oj.uz

Submission #670088

# Submission time Handle Problem Language Result Execution time Memory
670088 2022-12-08T05:14:43 Z Astrayt Sorting (IOI15_sorting) C++17
0 / 100
 503 ms 28872 KB 
#include <bits/stdc++.h>
using namespace std;
#define starburst ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//#define int long long
#define pii pair<int,int>
#define pb push_back

int findSwapPairs(int N, int *S, int M, int *X, int *Y, int *P, int *Q){
    int lb = 0, rb = M;
    while(lb != rb){
        int mid = (lb + rb) / 2;
        vector<int> cur(N), end(N), curid(N), endid(N);
        for(int i = 0; i < N; ++i) cur[i] = end[i] = S[i], curid[S[i]] = endid[S[i]] = i;
        for(int i = 0; i < mid; ++i){
            int x = X[i], y = Y[i];
            endid[end[x]] = y, endid[end[y]] = x;
            swap(end[x], end[y]);
        }
        int j = N - 1;
        for(int i = mid - 1; i >= 0; --i){
            while(j >= 0 && end[j] == j) j--;
            if(j < 0) break;
            int id = mid - i - 1;
            int x = X[id], y = Y[id];
            swap(curid[cur[x]], curid[cur[y]]);
            swap(cur[x], cur[y]);
            int a = end[j], b = j;
            swap(curid[a], curid[b]);
            swap(endid[a], endid[b]);
            swap(cur[curid[a]], cur[curid[b]]);
            swap(end[endid[a]], end[endid[b]]);
        }
        while(j >= 0 && end[j] == j) j--;
        if(j < 0) rb = mid;
        else lb = mid + 1;
    }
    vector<int> cur(N), end(N), curid(N), endid(N);
    for(int i = 0; i < N; ++i) cur[i] = end[i] = S[i], curid[S[i]] = endid[S[i]] = i;
    for(int i = 0; i < lb; ++i){
        int x = X[i], y = Y[i];
        endid[end[x]] = y, endid[end[y]] = x;
        swap(end[x], end[y]);
    }
    int j = N - 1;
    for(int i = lb - 1; i >= 0; --i){
        while(j >= 0 && end[j] == j) j--;
        if(j < 0) break;
        int id = lb - i - 1;
        int x = X[id], y = Y[id];
        swap(curid[cur[x]], curid[cur[y]]);
        swap(cur[x], cur[y]);
        for(auto x:cur) cout << x << ' ';
        cout << '\n';
        int a = end[j], b = j;
        P[id] = curid[a], Q[id] = curid[b];
        if(P[id] > Q[id]) swap(P[id], Q[id]);
        swap(curid[a], curid[b]);
        swap(endid[a], endid[b]);
        swap(cur[curid[a]], cur[curid[b]]);
        swap(end[endid[a]], end[endid[b]]);
        for(auto x:cur) cout << x << ' ';
        cout << '\n';
    }
    return lb;
}

/*void solve(){
    int n; cin >> n;
    int S[n];
    for(int i = 0; i < n; ++i) cin >> S[i];
    int m; cin >> m;
    int X[m], Y[m], P[m], Q[m];
    fill(P, P + m + 1, 0);
    fill(Q, Q + m + 1, 0);
    for(int i = 0; i < m; ++i) cin >> X[i] >> Y[i];
    int R = findSwapPairs(n, S, m, X, Y, P, Q);
    cout << R << '\n';
    for(int i = 0; i < R; ++i) cout << P[i] << ' ' << Q[i] << '\n';
}

signed main(){
    starburst
    int t = 1; //cin >> t;
    while(t--) solve();
}*/

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:52:18: warning: declaration of 'x' shadows a previous local [-Wshadow]
   52 |         for(auto x:cur) cout << x << ' ';
      |                  ^
sorting.cpp:49:13: note: shadowed declaration is here
   49 |         int x = X[id], y = Y[id];
      |             ^
sorting.cpp:61:18: warning: declaration of 'x' shadows a previous local [-Wshadow]
   61 |         for(auto x:cur) cout << x << ' ';
      |                  ^
sorting.cpp:49:13: note: shadowed declaration is here
   49 |         int x = X[id], y = Y[id];
      |             ^

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 300 KB Expected EOLN
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 300 KB Expected EOLN
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Incorrect 0 ms 212 KB Expected EOLN
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 300 KB Expected EOLN
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 503 ms 28872 KB Expected EOLN
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 503 ms 28872 KB Expected EOLN
2 Halted 0 ms 0 KB -