Submission #1240169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240169		simplemind_31	Sorting (IOI15_sorting)	C++20	Compilation error	0 ms	0 KiB

sorting

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]){
	vector<int> a(N), inv_a(N);
    // Apples b[p] = apple on plate p
    vector<int> b(N);
	for(int i=0;i<N;i++){
		b[i]=S[i];
	}
    for(int i = 0; i < N; i++){
        a[i] = i;
        inv_a[i] = i;
    }

    // Function to check feasibility for t rounds
    auto can = [&](int t){
        // copy plates
        vector<int> ca = a;
        for(int i = 0; i < t; i++) swap(ca[X[i]], ca[Y[i]]);
        // build pi: pi[i] = apple at slot i
        vector<int> pi(N);
        for(int i = 0; i < N; i++) pi[i] = b[ca[i]];
        vector<bool> vis(N, false);
        int cycles = 0;
        for(int i = 0; i < N; i++){
            if(!vis[i]){
                cycles++;
                int x = i;
                while(!vis[x]){
                    vis[x] = true;
                    x = pi[x];
                }
            }
        }
        // swaps needed = N - cycles
        return (N - cycles) <= t;
    };

    // binary search minimum t
    int lo = 0, hi = M, mid, best = M;
    while(lo <= hi){
        mid = (lo + hi) / 2;
        if(can(mid)){
            best = mid;
            hi = mid - 1;
        } else lo = mid + 1;
    }

    // simulate adversary fully for best rounds
    for(int i = 0; i < best; i++){
        swap(a[X[i]], a[Y[i]]);
        inv_a[a[X[i]]] = X[i];
        inv_a[a[Y[i]]] = Y[i];
    }
    // build final pi
    vector<int> pi(N);
    for(int i = 0; i < N; i++) pi[i] = b[a[i]];
    vector<bool> vis(N, false);
    vector<pair<int,int>> ops;
    // decompose into cycles and gather swaps
    for(int i = 0; i < N; i++){
        if(!vis[i]){
            vector<int> cyc;
            int x = i;
            while(!vis[x]){
                vis[x] = true;
                cyc.push_back(x);
                x = pi[x];
            }
            // break cycle of length l: swaps (cyc[0],cyc[j]) for j=1..l-1
            for(size_t j = 1; j < cyc.size(); j++){
                int u = cyc[0], v = cyc[j];
                // swap apples on plates a[u], a[v]
                ops.emplace_back(a[u], a[v]);
                swap(b[a[u]], b[a[v]]);
            }
        }
    }
    // fill remaining with dummy swaps
    while((int)ops.size() < best) ops.emplace_back(0, 0);

    // output
	for(int i=0;i<best;i++){
		P[i]=ops[i].first;
		Q[i]=ops[i].second;
	}
	return best;
    /*cout << best << '\n';
    for(int i = 0; i < best; i++){
        cout << ops[i].first << " " << ops[i].second << "\n";
    }*/
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:2:9: error: 'vector' was not declared in this scope
    2 |         vector<int> a(N), inv_a(N);
      |         ^~~~~~
sorting.cpp:2:16: error: expected primary-expression before 'int'
    2 |         vector<int> a(N), inv_a(N);
      |                ^~~
sorting.cpp:4:12: error: expected primary-expression before 'int'
    4 |     vector<int> b(N);
      |            ^~~
sorting.cpp:6:17: error: 'b' was not declared in this scope
    6 |                 b[i]=S[i];
      |                 ^
sorting.cpp:9:9: error: 'a' was not declared in this scope
    9 |         a[i] = i;
      |         ^
sorting.cpp:10:9: error: 'inv_a' was not declared in this scope
   10 |         inv_a[i] = i;
      |         ^~~~~
sorting.cpp: In lambda function:
sorting.cpp:16:16: error: expected primary-expression before 'int'
   16 |         vector<int> ca = a;
      |                ^~~
sorting.cpp:17:41: error: 'ca' was not declared in this scope; did you mean 'can'?
   17 |         for(int i = 0; i < t; i++) swap(ca[X[i]], ca[Y[i]]);
      |                                         ^~
      |                                         can
sorting.cpp:17:36: error: 'swap' was not declared in this scope
   17 |         for(int i = 0; i < t; i++) swap(ca[X[i]], ca[Y[i]]);
      |                                    ^~~~
sorting.cpp:19:16: error: expected primary-expression before 'int'
   19 |         vector<int> pi(N);
      |                ^~~
sorting.cpp:20:36: error: 'pi' was not declared in this scope; did you mean 'i'?
   20 |         for(int i = 0; i < N; i++) pi[i] = b[ca[i]];
      |                                    ^~
      |                                    i
sorting.cpp:20:44: error: 'b' was not declared in this scope
   20 |         for(int i = 0; i < N; i++) pi[i] = b[ca[i]];
      |                                            ^
sorting.cpp:20:46: error: 'ca' was not declared in this scope; did you mean 'can'?
   20 |         for(int i = 0; i < N; i++) pi[i] = b[ca[i]];
      |                                              ^~
      |                                              can
sorting.cpp:21:16: error: expected primary-expression before 'bool'
   21 |         vector<bool> vis(N, false);
      |                ^~~~
sorting.cpp:24:17: error: 'vis' was not declared in this scope
   24 |             if(!vis[i]){
      |                 ^~~
sorting.cpp:29:25: error: 'pi' was not declared in this scope; did you mean 'i'?
   29 |                     x = pi[x];
      |                         ^~
      |                         i
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:49:14: error: 'a' was not declared in this scope
   49 |         swap(a[X[i]], a[Y[i]]);
      |              ^
sorting.cpp:49:9: error: 'swap' was not declared in this scope
   49 |         swap(a[X[i]], a[Y[i]]);
      |         ^~~~
sorting.cpp:50:9: error: 'inv_a' was not declared in this scope
   50 |         inv_a[a[X[i]]] = X[i];
      |         ^~~~~
sorting.cpp:54:12: error: expected primary-expression before 'int'
   54 |     vector<int> pi(N);
      |            ^~~
sorting.cpp:55:32: error: 'pi' was not declared in this scope; did you mean 'i'?
   55 |     for(int i = 0; i < N; i++) pi[i] = b[a[i]];
      |                                ^~
      |                                i
sorting.cpp:55:40: error: 'b' was not declared in this scope
   55 |     for(int i = 0; i < N; i++) pi[i] = b[a[i]];
      |                                        ^
sorting.cpp:55:42: error: 'a' was not declared in this scope
   55 |     for(int i = 0; i < N; i++) pi[i] = b[a[i]];
      |                                          ^
sorting.cpp:56:12: error: expected primary-expression before 'bool'
   56 |     vector<bool> vis(N, false);
      |            ^~~~
sorting.cpp:57:12: error: 'pair' was not declared in this scope
   57 |     vector<pair<int,int>> ops;
      |            ^~~~
sorting.cpp:57:17: error: expected primary-expression before 'int'
   57 |     vector<pair<int,int>> ops;
      |                 ^~~
sorting.cpp:60:13: error: 'vis' was not declared in this scope
   60 |         if(!vis[i]){
      |             ^~~
sorting.cpp:61:20: error: expected primary-expression before 'int'
   61 |             vector<int> cyc;
      |                    ^~~
sorting.cpp:65:17: error: 'cyc' was not declared in this scope
   65 |                 cyc.push_back(x);
      |                 ^~~
sorting.cpp:66:21: error: 'pi' was not declared in this scope; did you mean 'i'?
   66 |                 x = pi[x];
      |                     ^~
      |                     i
sorting.cpp:69:17: error: 'size_t' was not declared in this scope
   69 |             for(size_t j = 1; j < cyc.size(); j++){
      |                 ^~~~~~
sorting.cpp:1:1: note: 'size_t' is defined in header '<cstddef>'; did you forget to '#include <cstddef>'?
  +++ |+#include <cstddef>
    1 | int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]){
sorting.cpp:69:35: error: 'cyc' was not declared in this scope
   69 |             for(size_t j = 1; j < cyc.size(); j++){
      |                                   ^~~
sorting.cpp:69:31: error: 'j' was not declared in this scope
   69 |             for(size_t j = 1; j < cyc.size(); j++){
      |                               ^
sorting.cpp:72:17: error: 'ops' was not declared in this scope
   72 |                 ops.emplace_back(a[u], a[v]);
      |                 ^~~
sorting.cpp:72:34: error: 'a' was not declared in this scope
   72 |                 ops.emplace_back(a[u], a[v]);
      |                                  ^
sorting.cpp:72:42: error: 'v' was not declared in this scope
   72 |                 ops.emplace_back(a[u], a[v]);
      |                                          ^
sorting.cpp:73:22: error: 'b' was not declared in this scope
   73 |                 swap(b[a[u]], b[a[v]]);
      |                      ^
sorting.cpp:73:17: error: 'swap' was not declared in this scope
   73 |                 swap(b[a[u]], b[a[v]]);
      |                 ^~~~
sorting.cpp:78:16: error: 'ops' was not declared in this scope
   78 |     while((int)ops.size() < best) ops.emplace_back(0, 0);
      |                ^~~
sorting.cpp:82:22: error: 'ops' was not declared in this scope
   82 |                 P[i]=ops[i].first;
      |                      ^~~