oj.uz

Submission #54513

# Submission time Handle Problem Language Result Execution time Memory
54513 2018-07-03T21:50:20 Z updown1 Sorting (IOI15_sorting) C++17
100 / 100
 452 ms 16120 KB 
/*
Binary Search on number of rounds
Move element to location so it will arrive and the correct final location at the end
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, rounds)
#define ffa ffi ffj
#define s <<" "<<
//#define c <<" : "<<
#define w cout
#define e "\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
const int MAXN=200000;
int start[MAXN], swi[MAXN][2], curpl[MAXN], curval[MAXN], fin[MAXN], locpl[MAXN], locval[MAXN];

bool works(int rounds, int N) {
    //w<< "trying" s rounds<<e;
    ffi fin[i] = curpl[i] = i, curval[i] = start[i];
    ffi locpl[curpl[i]] = i, locval[curval[i]] = i;
    ffj swap(fin[swi[j][0]], fin[swi[j][1]]);
    //ffi w<< fin[i] << " "; w<<e;
    int at = 0; /// next number to set to the correct location
    ffj {
        /// need to swap plates swi[j][0] and swi[j][1]
        int a = swi[j][0];
        int b = swi[j][1];
        swap (locpl[curpl[a]], locpl[curpl[b]]);
        swap (curpl[a], curpl[b]);
        //w<<j<<e; ffi w<< curpl[i]<<" "; w<<e;
        /// need to swap values swi[j][0] and swi[j][1]
        a = swi[j][0], b = swi[j][1];
        swap (locval[curval[a]], locval[curval[b]]);
        swap (curval[a], curval[b]);
        bool did = false;
        while (!did && at != N) {
            /// we want to end up in location "at" in final
            int pl = fin[at]; /// plate in the correct position
            int ind = locpl[pl]; /// index of the plate currently
            if (locval[at] == ind) {
                /// at is on the correct plate
                at++;
                continue;
            }
            /// need to swap values locval[at] and ind
            int a = locval[at];
            int b = ind;
            //w<< "for:" s at<<e; w<< a s b<<e;
            swap (locval[curval[a]], locval[curval[b]]);
            swap (curval[a], curval[b]);

            did = true, at++;
        }
    }
    bool did = false;
    while (!did && at != N) {
        /// we want to end up in location "at" in final
        int pl = fin[at]; /// plate in the correct position
        int ind = locpl[pl]; /// index of the plate currently
        if (locval[at] == ind) {
            /// at is on the correct plate
            at++;
            continue;
        }
        /// need to swap values locval[at] and ind but can't
        did = true;
    }
    //exit(0);
    //w<< at<<e;
    return at == N;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    ffi start[i] = S[i], swi[i][0] = X[i], swi[i][1] = Y[i];
    int a = 0, b = N;
    while (a != b) {
        int mid = (a+b)/2;
        if (works(mid, N)) b = mid;
        else a = mid+1;
    }
    /// Set P & Q
    int rounds = a;
    int x = 0;
    ffi fin[i] = curpl[i] = i, curval[i] = start[i];
    ffi locpl[curpl[i]] = i, locval[curval[i]] = i;
    ffj swap(fin[swi[j][0]], fin[swi[j][1]]);
    //ffi w<< fin[i] << " "; w<<e;
    int at = 0; /// next number to set to the correct location
    ffj {
        /// need to swap plates swi[j][0] and swi[j][1]
        int a = swi[j][0];
        int b = swi[j][1];
        swap (locpl[curpl[a]], locpl[curpl[b]]);
        swap (curpl[a], curpl[b]);
        //w<<j<<e; ffi w<< curpl[i]<<" "; w<<e;
        /// need to swap values swi[j][0] and swi[j][1]
        a = swi[j][0], b = swi[j][1];
        swap (locval[curval[a]], locval[curval[b]]);
        swap (curval[a], curval[b]);
        bool did = false;
        while (!did && at != N) {
            /// we want to end up in location "at" in final
            int pl = fin[at]; /// plate in the correct position
            int ind = locpl[pl]; /// index of the plate currently
            if (locval[at] == ind) {
                /// at is on the correct plate
                at++;
                continue;
            }
            /// need to swap values locval[at] and ind
            int a = locval[at];
            int b = ind;
            //w<< "for:" s at<<e; w<< a s b<<e;
            swap (locval[curval[a]], locval[curval[b]]);
            swap (curval[a], curval[b]);
            P[x] = a, Q[x] = b; x++;
            did = true, at++;
        }
    }
    while (x < rounds) {P[x] = 0; Q[x] = 0; x++;}


    return a;
}

Compilation message

sorting.cpp: In function 'bool works(int, int)':
sorting.cpp:18:11: warning: declaration of 'first' shadows a previous local [-Wshadow]
 #define a first
           ^
sorting.cpp:53:17: note: in expansion of macro 'a'
             int a = locval[at];
                 ^
sorting.cpp:18:11: note: shadowed declaration is here
 #define a first
           ^
sorting.cpp:33:13: note: in expansion of macro 'a'
         int a = swi[j][0];
             ^
sorting.cpp:19:11: warning: declaration of 'second' shadows a previous local [-Wshadow]
 #define b second
           ^
sorting.cpp:54:17: note: in expansion of macro 'b'
             int b = ind;
                 ^
sorting.cpp:19:11: note: shadowed declaration is here
 #define b second
           ^
sorting.cpp:34:13: note: in expansion of macro 'b'
         int b = swi[j][1];
             ^
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:18:11: warning: declaration of 'first' shadows a previous local [-Wshadow]
 #define a first
           ^
sorting.cpp:98:13: note: in expansion of macro 'a'
         int a = swi[j][0];
             ^
sorting.cpp:18:11: note: shadowed declaration is here
 #define a first
           ^
sorting.cpp:82:9: note: in expansion of macro 'a'
     int a = 0, b = N;
         ^
sorting.cpp:19:11: warning: declaration of 'second' shadows a previous local [-Wshadow]
 #define b second
           ^
sorting.cpp:99:13: note: in expansion of macro 'b'
         int b = swi[j][1];
             ^
sorting.cpp:19:11: note: shadowed declaration is here
 #define b second
           ^
sorting.cpp:82:16: note: in expansion of macro 'b'
     int a = 0, b = N;
                ^
sorting.cpp:18:11: warning: declaration of 'first' shadows a previous local [-Wshadow]
 #define a first
           ^
sorting.cpp:118:17: note: in expansion of macro 'a'
             int a = locval[at];
                 ^
sorting.cpp:18:11: note: shadowed declaration is here
 #define a first
           ^
sorting.cpp:98:13: note: in expansion of macro 'a'
         int a = swi[j][0];
             ^
sorting.cpp:19:11: warning: declaration of 'second' shadows a previous local [-Wshadow]
 #define b second
           ^
sorting.cpp:119:17: note: in expansion of macro 'b'
             int b = ind;
                 ^
sorting.cpp:19:11: note: shadowed declaration is here
 #define b second
           ^
sorting.cpp:99:13: note: in expansion of macro 'b'
         int b = swi[j][1];
             ^
sorting.cpp:80:39: warning: unused parameter 'M' [-Wunused-parameter]
 int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
                                       ^

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 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 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 3 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 3 ms 512 KB Output is correct
22 Correct 3 ms 512 KB Output is correct
23 Correct 3 ms 512 KB Output is correct
24 Correct 3 ms 512 KB Output is correct
25 Correct 3 ms 512 KB Output is correct
26 Correct 3 ms 512 KB Output is correct
27 Correct 3 ms 512 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 512 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Correct 4 ms 512 KB Output is correct
9 Correct 4 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 4 ms 512 KB Output is correct
13 Correct 4 ms 512 KB Output is correct
14 Correct 2 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 512 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Correct 4 ms 512 KB Output is correct
9 Correct 4 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 4 ms 512 KB Output is correct
13 Correct 4 ms 512 KB Output is correct
14 Correct 2 ms 512 KB Output is correct
15 Correct 205 ms 14448 KB Output is correct
16 Correct 328 ms 14840 KB Output is correct
17 Correct 366 ms 15580 KB Output is correct
18 Correct 77 ms 11132 KB Output is correct
19 Correct 204 ms 13796 KB Output is correct
20 Correct 226 ms 14176 KB Output is correct
21 Correct 229 ms 14200 KB Output is correct
22 Correct 195 ms 15736 KB Output is correct
23 Correct 285 ms 16108 KB Output is correct
24 Correct 434 ms 15864 KB Output is correct
25 Correct 451 ms 15708 KB Output is correct
26 Correct 313 ms 14328 KB Output is correct
27 Correct 302 ms 13712 KB Output is correct
28 Correct 452 ms 15608 KB Output is correct
29 Correct 321 ms 15108 KB Output is correct
30 Correct 178 ms 12884 KB Output is correct
31 Correct 341 ms 15436 KB Output is correct
32 Correct 214 ms 15572 KB Output is correct
33 Correct 372 ms 15864 KB Output is correct
34 Correct 339 ms 15732 KB Output is correct
35 Correct 155 ms 13532 KB Output is correct
36 Correct 57 ms 12024 KB Output is correct
37 Correct 285 ms 16120 KB Output is correct
38 Correct 245 ms 15608 KB Output is correct
39 Correct 253 ms 15708 KB Output is correct