oj.uz

Submission #43775

# Submission time Handle Problem Language Result Execution time Memory
43775 2018-03-23T07:23:53 Z PowerOfNinjaGo Sorting (IOI15_sorting) C++14
100 / 100
 611 ms 21048 KB 
//Power Of Ninja Go
#include <bits/stdc++.h>
#ifdef atom
#include "grader.cpp"
#else
#include "sorting.h"
#endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii;
#define X first
#define Y second
#define vi vector<int>
#define vii vector< ii >
#define pb push_back
const int maxn = 2e5+5;
int a[3*maxn], b[3*maxn];
int x[3*maxn], y[3*maxn];
int arr[maxn];
int revnow[maxn], realnow[maxn], realend[maxn], revend[maxn];
int n, m;
bool works(int k)
{
    //printf("try %d\n", k);
    for(int i = 0; i< n; i++)
    {
        realend[i] = arr[i];
        realnow[i] = arr[i];
        revnow[arr[i]] =  i;
        revend[arr[i]] = i;
    }
    for(int i = 0; i< k; i++)
    {
        int p = x[i], q = y[i];
        int s = realend[p], t = realend[q];
        swap(realend[p], realend[q]);
        swap(revend[s], revend[t]);
    }
    int cur = 0;
    //for(int i = 0; i< n; i++) printf("%d %d\n", realnow[i], realend[i]);
    for(int i = 0; i< k; i++)
    {
        //printf("move %d\n", i);
        int p = x[i], q = y[i];
        int s = realnow[p], t = realnow[q];
        swap(revnow[s], revnow[t]);
        swap(realnow[p], realnow[q]);
        //for(int i = 0; i< n; i++) printf("%d %d\n", realnow[i], realend[i]);
        while(cur< n && realend[cur] == cur)
        {
            cur++;
            continue;
        }
        if(cur< n)
        {

            int rep = realend[cur];
            // swap rep and cur in the original array
            int s = revnow[rep], t = revnow[cur];
            swap(realnow[s], realnow[t]);
            swap(revnow[rep], revnow[cur]);
            a[i] = s, b[i] = t;
            //printf("swap %d %d\n", s, t);
            //swap rep and cur in the final array
            s = cur, t = revend[cur];
            //printf("swapend %d %d\n", s, t);
            swap(realend[s], realend[t]);
            swap(revend[rep], revend[cur]);
            cur++;
        }
        else a[i] = b[i] = 0;
        while(cur< n && realend[cur] == cur)
        {
            cur++;
            continue;
        }
    }
    return cur == n;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
    n = N; m = M;
    for(int i = 0; i< N; i++) arr[i] = S[i];
    for(int i = 0; i< M; i++) x[i] = X[i], y[i] = Y[i];
    bool alreadySorted = 1;
    for(int i = 0; i< N; i++) if(arr[i] != i) alreadySorted = 0;
    if(alreadySorted)
    {
        return 0;
    }
    int lo = 1, hi = M;
    while(lo< hi)
    {
        int mid = (lo+hi)/2;
        if(works(mid)) hi = mid;
        else lo = mid+1;
    }
    works(lo);
    for(int i = 0; i< lo; i++) P[i] = a[i], Q[i] = b[i];
    return lo;
}

Compilation message

sorting.cpp: In function 'bool works(int)':
sorting.cpp:58:17: warning: declaration of 's' shadows a previous local [-Wshadow]
             int s = revnow[rep], t = revnow[cur];
                 ^
sorting.cpp:44:13: note: shadowed declaration is here
         int s = realnow[p], t = realnow[q];
             ^
sorting.cpp:58:34: warning: declaration of 't' shadows a previous local [-Wshadow]
             int s = revnow[rep], t = revnow[cur];
                                  ^
sorting.cpp:44:29: note: shadowed declaration is here
         int s = realnow[p], t = realnow[q];
                             ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 380 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 412 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 380 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 412 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 3 ms 384 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 380 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 412 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 3 ms 356 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 3 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 4 ms 384 KB Output is correct
19 Correct 2 ms 360 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 4 ms 640 KB Output is correct
22 Correct 3 ms 640 KB Output is correct
23 Correct 3 ms 640 KB Output is correct
24 Correct 4 ms 640 KB Output is correct
25 Correct 4 ms 640 KB Output is correct
26 Correct 4 ms 640 KB Output is correct
27 Correct 4 ms 632 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 4 ms 640 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 3 ms 640 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 4 ms 768 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 3 ms 640 KB Output is correct
12 Correct 3 ms 640 KB Output is correct
13 Correct 3 ms 512 KB Output is correct
14 Correct 3 ms 512 KB Output is correct

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 4 ms 640 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 3 ms 640 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 4 ms 768 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 3 ms 640 KB Output is correct
12 Correct 3 ms 640 KB Output is correct
13 Correct 3 ms 512 KB Output is correct
14 Correct 3 ms 512 KB Output is correct
15 Correct 434 ms 18676 KB Output is correct
16 Correct 537 ms 18984 KB Output is correct
17 Correct 530 ms 19888 KB Output is correct
18 Correct 44 ms 10488 KB Output is correct
19 Correct 195 ms 18412 KB Output is correct
20 Correct 254 ms 18936 KB Output is correct
21 Correct 235 ms 18936 KB Output is correct
22 Correct 483 ms 20344 KB Output is correct
23 Correct 510 ms 20688 KB Output is correct
24 Correct 611 ms 20480 KB Output is correct
25 Correct 449 ms 20216 KB Output is correct
26 Correct 490 ms 18936 KB Output is correct
27 Correct 315 ms 18300 KB Output is correct
28 Correct 533 ms 20216 KB Output is correct
29 Correct 526 ms 19676 KB Output is correct
30 Correct 285 ms 17656 KB Output is correct
31 Correct 580 ms 20060 KB Output is correct
32 Correct 540 ms 20084 KB Output is correct
33 Correct 582 ms 20364 KB Output is correct
34 Correct 560 ms 20324 KB Output is correct
35 Correct 191 ms 18244 KB Output is correct
36 Correct 73 ms 16760 KB Output is correct
37 Correct 379 ms 21048 KB Output is correct
38 Correct 322 ms 20032 KB Output is correct
39 Correct 327 ms 20292 KB Output is correct