I'll just combine two previous hints.
Use bubble sort and THEN use random.

Hi, I'm still getting WA-1, can anybody give me answers to these tests:

80 60
60 80
60 60

Thanks.

a-b and c-d are close, but not touching each other.

-2 0 0
-1 0 0
0 1 0
0 1000000 1

In this test all numbers are big (~1e9), so it can be precision errors/overflow. You should use NTT with big modulo to avoid doubles

Use long long

The width of the last column of ranklist, "Last AC", is a little narrower than needed. The ranklist table always displayes abnormal. Please can you take a look?

And so does the bottom ranklist table in the author page.

Solved the problem using segment tree.
Im using VC++ 12 and it's giving the correct answer for the sample.
Still while sending (VC++ 2010) im getting WA 1. Changing it to G++ C++ 11 gives AC. What's the difference and why am i getting WA 1 when i choose VC++?

Code:
#include <iostream>
#include <vector>
using namespace std;
const int MAXN=100000;
pair<int, int> t[4*MAXN];
int z=1;


void build_tree(int v, int tl, int tr)
{
    if (tl==tr)
    {
        t[v]=make_pair(1,z++);
        return;
    }
    int tm=(tl+tr)/2;
    build_tree(2*v, tl, tm); build_tree(2*v+1, tm+1, tr);
    t[v].first=t[2*v].first+t[2*v+1].first;
    t[v].second=-1;
}


int req(int v, int tl, int tr, int n)
{
    if (tl==tr)
    {
        --t[v].first;
        return t[v].second;
    }
    int tm=(tl+tr)/2;
    t[v].first--;
    if (t[2*v].first>=n)
        req(2*v, tl, tm, n);
    else
        req(2*v+1, tm+1,tr,n-t[2*v].first);




}


int main()
{
    int n, k; cin>>n>>k;
    build_tree(1,1,100000);
    int cur=k;
    for (int i=0; i<n; ++i)
    {
        int h=req(1,1,100000, cur);
        cout<<h<<" ";
        if (i==n-1)
            break;
        cur=(cur-1+k)%(n-1-i);
        if (cur==0)
            cur+=n-1-i;
    }
}

Edited by author 10.03.2013 07:20

He donated all the money to the poor and went to bed with a clear conscience...

WpKRwvgKenn
output shold be
"WpKRwvgKenneKgvwRKpW"
not
"WpKRwvgKennneKgvwRKpW"

Этот код работает везде, кроме как на этом сайте
Runtime error test 1. Почему???

import sys
array4 = dict()
result = ""
for i in sys.stdin.read().split("\n")[1:]:
    array4[str(i.split(" ")[0])] = str(i.split(" ")[1])
def QSort(arr3):
    if len(arr3) < 2:
        return arr3
    else:
        privot, do3, sered, posle = int(arr3[list(arr3.keys())[0]]), dict(), dict(), dict()
        for x, i in arr3.items():
            if int(i) > privot:
                do3[x] = i
            elif int(i) < privot:
                posle[x] = i
            else:
                sered[x] = i
    return {**QSort(do3), **sered, **QSort(posle)}
for t, y in QSort(array4).items():
    result += f"{t} {y}\n"
print(result.strip('\n'))

# include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define vec vector
#define int long long
#define ld long double

#define f first
#define s second

#define pb push_back

#define fe(x, a) for (auto& x : a)

#define pw(x) (1ll << x)
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using pii = pair<int, int>;

const int mod = 1e9 + 7;
const ll OO = 1e16;
const int N = 1e5 + 2;
const ld eps = 1e-3;

template<typename T>
bool umn(T &a, T b) { return a > b ? (a = b, 1) : 0; }

template<typename T>
bool umx(T &a, T b) { return a < b ? (a = b, 1) : 0; }

void solve() {
    int n, best = -1, ans = 0;
    cin >> n;
    set<pii> setik;
    for (int i = 0, x; i < n + 1; ++i) {
        x = -OO;
        if (i < n)
            cin >> x;
        if (i && x < (*setik.begin()).f)
            if (umx(best, i - (*setik.begin()).s - !(*setik.begin()).s))
                ans = (*setik.begin()).s;

        setik.insert({x, i});
    }
    cout << ans + 1;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
//    cin >> t;
    while (t--)
        solve();
}

Input:
9
16372 24788
000010111
001111101
010010001
010011001
111100101
010100100
110011000
100000000
111110000

Possible answer (a's should be the same, d's can differ in you answer):
163720
000000000
000000d0d
0000d000d
0000dd00d
00dd00d0d
000d00d00
0d00dd000
000000000
0dddd0000

Matrix for the graph in the answer:
000010111
001111000
010000000
010000000
110000000
010000000
100000000
100000000
100000000

Edited by author 12.05.2023 13:49

If you have a mistake, most likely you delete connections of the input graph in a wrong way.
And most likely, because you search the connected components incorrectly.

If you are solving using formula, there are some corner cases.

IN
0 0
0 0
OUT
0

IN
17 0
0 17
OUT
17

And just some random test.

IN
7 9
6 8
OUT
15.165177459575631

Who can tell me…………
Why got WA#12?

#include <iostream>

int main()
{
    long long int y1;
    int y2, y3, y4;

    std::cin;
    std::cin >> y1;
    y4 = y1 / 16777216;
    y1 = y1 % 16777216;
    y3 = y1 / 65536;
    y1 = y1 % 65536;
    y2 = y1 / 256;
    y1 = y1 % 256;
    y1 = y1 * 16777216 + y2 * 65536 + y3 * 256 + y4;
    std::cout << y1;
    return 0;
}
в данном коде есть проблема: в данном компиляторе первый cin ничего не делает и второй получает на вход строку.

La testoj estis kreitaj uzante hazardigilon en programo kiu ricevis AC:
12 10 8 -> 21 3
12 15 13 -> 36 3
10 18 12 -> 31 3
10 9 8 -> 21 3
20 6 16 -> 45 12
7 7 7 -> 18 3
13 15 1 -> 0 0
18 19 4 -> 9 3
18 19 19 -> 54 3
0 1 13 -> 12 12
7 10 7 -> 18 3
6 2 16 -> 27 16
2 5 10 -> 13 7
19 18 14 -> 39 3
18 3 14 -> 42 13
19 7 2 -> 6 3
0 8 2 -> 1 0
10 13 16 -> 35 5
7 9 11 -> 24 4
16 8 14 -> 39 8
7 10 7 -> 18 3
4 2 12 -> 19 12
11 15 1 -> 0 0
5 20 1 -> 0 0
8 13 8 -> 21 3
18 2 19 -> 54 19
2 12 20 -> 23 10
5 10 16 -> 25 8
10 1 3 -> 9 4
17 12 2 -> 6 3
2 7 3 -> 6 0
14 19 19 -> 46 3
3 0 5 -> 11 7
6 7 12 -> 23 7
14 11 7 -> 18 3
11 3 6 -> 18 5
2 11 10 -> 13 1
17 5 11 -> 33 8
10 16 12 -> 31 3
7 19 15 -> 28 3
17 15 5 -> 12 3
19 5 12 -> 36 9
4 12 6 -> 13 0
6 9 17 -> 28 10
4 4 18 -> 25 16
16 3 17 -> 48 16
13 0 2 -> 6 4
8 18 9 -> 24 0
3 19 8 -> 13 0
17 16 9 -> 24 3
11 5 6 -> 18 3
20 3 8 -> 24 7
1 9 13 -> 14 5
16 2 10 -> 30 10
15 2 2 -> 6 3
6 1 15 -> 26 16
5 14 19 -> 28 7
18 10 1 -> 3 3
20 1 2 -> 6 3
1 5 5 -> 6 1
3 3 12 -> 17 11
10 5 17 -> 36 14
8 19 7 -> 18 0
3 5 8 -> 13 5
18 8 15 -> 42 9
20 14 3 -> 9 3
4 0 16 -> 24 18
15 3 5 -> 15 4
7 4 9 -> 22 7
7 14 20 -> 33 8
8 10 3 -> 6 1
16 0 1 -> 3 3
13 2 3 -> 9 3
8 2 19 -> 34 19
6 7 10 -> 21 5
20 6 6 -> 18 3
11 7 1 -> 3 3
17 16 15 -> 42 3
5 11 2 -> 3 0
20 9 3 -> 9 3
8 2 4 -> 12 4
6 13 6 -> 15 0
12 1 3 -> 9 4
1 8 15 -> 16 8
10 17 16 -> 35 3
9 0 15 -> 33 17
4 2 18 -> 25 18
8 10 6 -> 15 3
12 0 13 -> 37 15
20 5 20 -> 57 17
4 14 20 -> 27 8
4 1 16 -> 23 17
17 13 6 -> 15 3
18 8 12 -> 33 6
20 3 3 -> 9 3
16 19 6 -> 15 3
0 13 14 -> 13 1
3 4 18 -> 23 16
4 10 15 -> 22 7
2 14 7 -> 10 0

For me from statement was clear, that there are always solutions, either one or multiple. But in test 5 there is no solution. You have to print IMPOSSIBLE in this case.

Anti-hash testcases are added, so I guess intended solution isn't hashing. However I can't think of any.

My code was failing WA#3 until I got this case working:
4
3 1 1 1
14
1 1 3  1 2 3  2 2 3  2 4 3  3 4 3  4 4 3  2 3 3
1 1 1  1 2 1  2 2 1  1 4 1  2 4 1  3 4 1  3 3 1
> 11000000111111


Other:


8
0 0 1 1 0 0 1 1
35
1 2 1  1 1 1  1 3 1  2 3 1  1 6 1  2 5 1  5 6 1
5 5 1  6 6 1  3 4 1  3 3 1  4 4 1  4 7 1  4 6 1
5 7 1  1 2 0  1 1 0  1 3 0  2 3 0  1 6 0  2 5 0
5 6 0  5 5 0  6 6 0  3 4 0  3 3 0  4 4 0  4 7 0
4 6 0  5 7 0  1 7 2  1 2 2  1 1 2  3 3 2  5 5 2
> 00111100011111111111111100011100000


9
1 1 9 9 1 9 9 1 1
70
1 9 9
1 9 1
1 9 5
1 1 1  2 2 1  3 3 9  4 4 9  5 5 1  6 6 9  7 7 9  8 8 1  9 9 1
1 1 9  2 2 9  3 3 1  4 4 1  5 5 9  6 6 1  7 7 1  8 8 9  9 9 9
1 2 1  2 3 1  3 4 1  4 5 1  5 6 1  6 7 1  7 8 1  8 9 1
1 2 9  2 3 9  3 4 9  4 5 9  5 6 9  6 7 9  7 8 9  8 9 9
1 3 9  1 4 9  1 5 9  1 6 9  1 7 9  1 8 9  1 9 9
3 4 1  2 4 1  3 5 1  2 5 1
3 4 9  2 4 9  3 5 9  2 5 9
1 1 5  1 2 5  1 3 5  2 2 5  3 3 5  8 9 5  7 9 5  9 9 5  6 6 5
3 3 1  3 4 1  3 5 1  4 5 1  5 5 1  5 6 1  5 7 1  6 7 1  7 7 1
> 1101111111110000000001101101101111110111111101111111000000000001111100


7
1 1 1 3 1 1 1
11
4 4 3  3 4 3  4 5 3  3 5 3  1 3 3  5 8 3  3 3 3  5 5 3
4 4 1  1 7 3  1 7 1
> 11110000011