Are there beautifull solution? The one other from bruteforce

My solution is O(tl^3logn) , but its performance is good.

#include<bits/stdc++.h>
#include<math.h>
using namespace std;
int main()
{
    int N, sum = 0;
    cin>> N;

    if(N > 0)
    {
        for(int i = 1; i <= N; i++)
        {
            sum = sum + i;
        }
    }
    else if(N <= 0)
    {
        for(int i = N; i <= 1; i++)
        {
            sum = sum + i;
        }
    }

    cout<< sum << endl;

    return 0;
}

a=int(input())
b=0
for i in range(a):
    n,l=map(int, input().split())
    b=b*10+n+l
print('0'*(a-len(str(b))),b, sep='')

If you calculate with formulas, then long long is not enough. You can use __int128. You can't read and write it, but you can cast it to and from other integer types.

Bruteforcing in range [0, 4e7] gives WA9, bruteforcing in range [1e8-4e7,1e8] gives AC

Edited by author 28.07.2022 20:34

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n1,n2;
    int a[n1],b[n2];
    cin>>n1;
    for(int k=0;k<n1;k++) cin>>a[k];
    cin>>n2;
    for(int k=0;k<n2;k++) cin>>b[k];
    sort(a,a+n1);
    sort(b,b+n2);
    int i=0,j=n2-1;
    bool ans=false;
    while(i<n1&&j>=0){
        if(a[i]+b[j]==10000){
            ans=true;
            break;
        }
        else if(a[i]+b[j]>10000){
            j--;
        }
        else{
            i++;
        }
    }
    if(ans) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

/*
::::
author:@DEANNOS at CODEFORCES 2022
::::
*/



#include <bits/stdc++.h>
//using policy based stl
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace std;
#define endl "\n"
#define mod 1000000007
#define ll long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define pll pair<ll, ll>
#define pii pair<int, int>
#define ld  long double
#define ff  first
#define ss  second
#define vs  vector<string>
#define vpll vector<pll>
#define vb  vector<bool>
#define pb push_back
#define bg begin()
#define mp make_pair
#define ed end()
#define gi greater<int> ()
#define srt(v) (sort(all())
#define all(c) (c).begin(), (c).end()
#define sz(x) (int)(x).size()
#define fo(i,n) for(ll i=0;i<n;i++)
#define Fo(i,k,n) for(ll i=k;i<n;i++)
const int INF = 1000000000;
const int MAX_N = 2e5;



/*
int fastpower(int x, int y, int mod)
{
    int res = 1;
    x = x % mod;
    if (x == 0)
    {
     return 0;
    }
    while (y > 0)
    {
        if (y & 1)
        {
         res = (res*x) % mod;
        }
        y = y>>1;
        x = (x*x) % mod;
    }
    return res;
}
*/

/*
int GCD(int a,int b)
{
 while(b!=0)
 {
  int rem=a%b;
  a=b;
  b=rem;
 }
 return a;
}
*/

ll integer(ll a)
{
    return a >= 0 ? a : -a;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    ll ans1 = 1, ans2 = 2, mx = 0;
    ll a;
    cin >> a;
    for (int i = 1; i < n; i++)
    {
        ll b;
        cin >> b;
        if (integr(a - b) > mx)
        {
            mx = integer(a - b);
            ans1 = i;
            ans2 = i + 1;
        }
        a = b;
    }
    cout << ans1 << ans2 << endl;
    return 0;

}

1. Вы пишите:найти для экскурсии кратчайший маршрут, начинающийся и заканчивающийся в одном и том же месте, т.е. количество перекрестков в маршруте должно быть N+1?. в след. абзаце: Все числа x1, …, xk должны быть различны. т.е.  либо маршрут не должен заканчиваться на том же перекресте где начался либо должно быть дополнительное условие Х1=Хк. это принципиальная ошибка в условии.
2. пример который вы привели:
5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20
4 3
1 2 10
1 3 20
1 4 30
-1
дает результат:
1 3 5 2
No solution.
а куда вы в первом тесте дели перекрестов №4?
3. Исходя из примера маршрут не должен содержать в себе все перекрестки?

Ошибки очевидны. те решения, что вы приняли - частные, случайно полученные.
Уточняйте условия и проверяйте свое решение.

Edited by author 07.11.2014 13:33

Что-то я не совсем понял условие задачи.
"M двусторонних дорог" - т.е. вроде как не ор. граф.
Но пример и решение говорят, о том, что скорее это все таки ор. граф.

1 3 300
3 1 10

Так есть ориентация у ребер или нету?

6 6
1 2 1
1 3 1
2 3 10
4 5 2
4 6 2
6 5 2
-1

ANS:
4 5 6

Don't calculate second probability, instead calculate probability that sergey will come to the cafe in the same time both on the first path and on the second. Using this probability you can easily calculate second answer

Check your "strong connected components" code

89 2
12 apr 17
21 jun 2

8.4874959390
22.5720084367

-----

15.7 3
1 apr 13
21 dec 8
12 oct 17

70.5459180884
19.4871801373
10.3882860539

-----

-71 3
25 feb 5
3 aug 15
6 oct 10

3.6840008337
0.0000000000
22.5788661148

-----

13.5 6
1 jan 15
1 mar 15
1 may 15
1 jul 15
1 sep 15
1 nov 15

33.5814351330
41.8302148985
44.0959307671
47.1958719101
46.8042204476
34.9899114970

-----

* deleted *

Edited by moderator 23.07.2022 20:33

почему именно stable_sort?  c++
простой sort нельзя?  c++

1 1
1 1
3
100 1 0
100 1 1
0 1 0

answer: 1 0

27 5
O-O-O-O-O-O-O O-O-O-O-O-O-O
|\ \| | | |/| |\| | | |/ /|
O-O O O O O O-O O O O O O-O
|/ / /| |\ \| |/ /| |\ \ \|
O-O-O-O-O-O-O O-O-O-O-O-O-O

Answer: Just a picture

Anti-hash tests are added. Please choose mod = 2^64 and strange p in case of being hacked.