oj.uz

Submission #148133

# Submission time Handle Problem Language Result Execution time Memory
148133 2019-08-31T14:10:03 Z WhipppedCream Sorting (IOI15_sorting) C++17
100 / 100
 630 ms 29568 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 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 400 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 400 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 400 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 400 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 508 KB Output is correct
12 Correct 2 ms 504 KB Output is correct

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 400 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 400 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 508 KB Output is correct
12 Correct 2 ms 504 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 3 ms 380 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 3 ms 760 KB Output is correct
22 Correct 3 ms 760 KB Output is correct
23 Correct 3 ms 760 KB Output is correct
24 Correct 3 ms 760 KB Output is correct
25 Correct 3 ms 760 KB Output is correct
26 Correct 3 ms 760 KB Output is correct
27 Correct 3 ms 764 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 632 KB Output is correct
2 Correct 3 ms 628 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 2 ms 480 KB Output is correct
5 Correct 3 ms 636 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 4 ms 632 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Correct 3 ms 632 KB Output is correct
11 Correct 4 ms 632 KB Output is correct
12 Correct 3 ms 632 KB Output is correct
13 Correct 3 ms 632 KB Output is correct
14 Correct 3 ms 636 KB Output is correct

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 632 KB Output is correct
2 Correct 3 ms 628 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 2 ms 480 KB Output is correct
5 Correct 3 ms 636 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 4 ms 632 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Correct 3 ms 632 KB Output is correct
11 Correct 4 ms 632 KB Output is correct
12 Correct 3 ms 632 KB Output is correct
13 Correct 3 ms 632 KB Output is correct
14 Correct 3 ms 636 KB Output is correct
15 Correct 354 ms 26304 KB Output is correct
16 Correct 452 ms 26872 KB Output is correct
17 Correct 590 ms 28380 KB Output is correct
18 Correct 49 ms 18552 KB Output is correct
19 Correct 319 ms 26828 KB Output is correct
20 Correct 317 ms 27768 KB Output is correct
21 Correct 345 ms 27768 KB Output is correct
22 Correct 402 ms 23852 KB Output is correct
23 Correct 367 ms 29428 KB Output is correct
24 Correct 630 ms 28920 KB Output is correct
25 Correct 620 ms 28636 KB Output is correct
26 Correct 439 ms 27772 KB Output is correct
27 Correct 385 ms 26844 KB Output is correct
28 Correct 559 ms 28740 KB Output is correct
29 Correct 540 ms 28252 KB Output is correct
30 Correct 311 ms 26360 KB Output is correct
31 Correct 564 ms 28764 KB Output is correct
32 Correct 381 ms 28336 KB Output is correct
33 Correct 616 ms 28856 KB Output is correct
34 Correct 504 ms 28804 KB Output is correct
35 Correct 305 ms 26584 KB Output is correct
36 Correct 79 ms 25208 KB Output is correct
37 Correct 508 ms 29568 KB Output is correct
38 Correct 469 ms 28588 KB Output is correct
39 Correct 489 ms 28756 KB Output is correct