oj.uz

Submission #669718

# Submission time Handle Problem Language Result Execution time Memory
669718 2022-12-07T06:59:45 Z victor_gao Sorting (IOI15_sorting) C++17
20 / 100
 1000 ms 408 KB 
#include "sorting.h"
#include <bits/stdc++.h>
#define MAXN 200015
using namespace std;
int bk[MAXN],pos_bk[MAXN],pre[MAXN],pos_pre[MAXN];
int solve(int N,int n,int S[],int P[],int Q[],int X[],int Y[]){
    int now=0,cnt_same=0;
    for (int i=0;i<N;i++){
        bk[i]=i; pos_bk[i]=i;
        pre[i]=S[i];  pos_pre[S[i]]=i;
        if (pre[i]==i) cnt_same++;
    }
    for (int i=n-1;i>=0;i--){
        swap(bk[X[i]],bk[Y[i]]);
        pos_bk[bk[X[i]]]=X[i];
        pos_bk[bk[Y[i]]]=Y[i];
    }
    for (int i=0;i<n;i++){
        if (cnt_same==N) return i;
        if (pre[X[i]]==X[i]) cnt_same--;
        if (pre[Y[i]]==Y[i]) cnt_same--;
        swap(pre[X[i]],pre[Y[i]]);
        if (pre[X[i]]==X[i]) cnt_same++;
        if (pre[Y[i]]==Y[i]) cnt_same++;
        pos_pre[pre[X[i]]]=X[i];
        pos_pre[pre[Y[i]]]=Y[i];
        swap(bk[X[i]],bk[Y[i]]);
        pos_bk[bk[X[i]]]=X[i];
        pos_bk[bk[Y[i]]]=Y[i];
        now=i;
        while (now<N&&pos_pre[now]==pos_bk[now])
            now++;
        if (now>=N) continue;
        P[i]=pos_pre[now]; Q[i]=pos_bk[now];
        if (pre[P[i]]==P[i]) cnt_same--;
        if (pre[Q[i]]==Q[i]) cnt_same--;
        swap(pre[pos_pre[now]],pre[pos_bk[now]]);
        if (pre[P[i]]==P[i]) cnt_same++;
        if (pre[Q[i]]==Q[i]) cnt_same++;
        pos_pre[pre[pos_pre[now]]]=pos_pre[now];
        pos_pre[pre[pos_bk[now]]]=pos_bk[now];
    }
    bool flag=1;
    for (int i=0;i<N;i++){
        if (pre[i]!=i) flag=0;
    }
    if (flag) return n;
    else return 1e9;
}
int solve1(int N,int n,int S[],int P[],int Q[],int X[],int Y[]){
    for (int i=0;i<N;i++){
        bk[i]=i; pos_bk[i]=i;
        pre[i]=S[i];  pos_pre[S[i]]=i;
    }
    for (int i=n-1;i>=0;i--){
        swap(bk[X[i]],bk[Y[i]]);
        pos_bk[bk[X[i]]]=X[i];
        pos_bk[bk[Y[i]]]=Y[i];
    }
    int now=0;
    for (int i=0;i<n;i++){
        bool flag=1;
        for (int j=0;j<N;j++){
            if (pre[j]!=j){
                flag=0;
                break;
            } 
        }
        if (flag)
            return i;
        swap(pre[X[i]],pre[Y[i]]);
        pos_pre[pre[X[i]]]=X[i];
        pos_pre[pre[Y[i]]]=Y[i];
        swap(bk[X[i]],bk[Y[i]]);
        pos_bk[bk[X[i]]]=X[i];
        pos_bk[bk[Y[i]]]=Y[i];
        now=i;
        while (now<N&&pos_pre[now]==pos_bk[now])
            now++;
        if (now>=N) continue;
        P[i]=pos_pre[now]; Q[i]=pos_bk[now];
        swap(pre[pos_pre[now]],pre[pos_bk[now]]);
        pos_pre[pre[pos_pre[now]]]=pos_pre[now];
        pos_pre[pre[pos_bk[now]]]=pos_bk[now];
    }
    bool flag=1;
    for (int i=0;i<N;i++){
        if (pre[i]!=i) flag=0;
    }
    if (flag) return n;
    else return 1e9;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    /*
    int l=0,r=M;
    while (l<r){
        int mid=(l+r)>>1;
        if (solve(N,mid,S,P,Q,X,Y)<1e8) r=mid;
        else l=mid+1;
    }
    return solve(N,l,S,P,Q,X,Y);
    */
    int mn=1e9,pos;
    for (int i=0;i<M;i++){
        int need=solve1(N,i,S,P,Q,X,Y);
        if (need<1e8){
            if (mn>need){
                mn=need;
                pos=i;
            }
        }
    }
    return solve1(N,pos,S,P,Q,X,Y);
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:113:18: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
  113 |     return solve1(N,pos,S,P,Q,X,Y);
      |            ~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 76 ms 340 KB Output is correct
11 Correct 79 ms 340 KB Output is correct
12 Correct 74 ms 340 KB Output is correct

Subtask #3
0 / 16.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 Correct 68 ms 340 KB Output is correct
4 Correct 72 ms 340 KB Output is correct
5 Correct 74 ms 340 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 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 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 76 ms 340 KB Output is correct
11 Correct 79 ms 340 KB Output is correct
12 Correct 74 ms 340 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 68 ms 340 KB Output is correct
16 Correct 72 ms 340 KB Output is correct
17 Correct 74 ms 340 KB Output is correct
18 Incorrect 1 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 842 ms 404 KB Output is correct
2 Execution timed out 1096 ms 408 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 842 ms 404 KB Output is correct
2 Execution timed out 1096 ms 408 KB Time limit exceeded
3 Halted 0 ms 0 KB -