# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
838372 | 2023-08-26T17:52:45 Z | AbdelmagedNour | Sorting (IOI15_sorting) | C++17 | 80 ms | 19540 KB |
#include <bits/stdc++.h> using namespace std; //#include "grader.cpp" #include "sorting.h" bool check(int T,int N,int M,int S[],int X[],int Y[],int P[],int Q[]){ vector<vector<int>>nxt(T+1,vector<int>(N)); for(int i=0;i<N;i++)nxt[T][i]=i; for(int i=T-1;i>=0;i--){ for(int j=0;j<N;j++){ nxt[i][j]=nxt[i+1][j]; } swap(nxt[i][X[i]],nxt[i][Y[i]]); } int a[N]; for(int i=0;i<N;i++)a[i]=S[i]; for(int i=0;i<T;i++){ int j=0; swap(a[X[i]],a[Y[i]]); while(j<N&&a[j]==nxt[i+1][j])j++; if(j==N)P[i]=Q[i]=0; else P[i]=j,Q[i]=find(nxt[i+1].begin(),nxt[i+1].end(),a[j])-nxt[i+1].begin(); swap(a[P[i]],a[Q[i]]); } return is_sorted(a,a+N); } int findSwapPairs(int N,int S[],int M,int X[],int Y[],int P[],int Q[]){ int l=1,r=M,res=1; while(l<=r){ int md=(l+r)>>1; if(check(md,N,M,S,X,Y,P,Q))r=(res=md)-1; else l=md+1; } return res; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 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 | 1 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 212 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 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 | 1 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 212 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
8 | Correct | 1 ms | 212 KB | Output is correct |
9 | Correct | 1 ms | 212 KB | Output is correct |
10 | Correct | 1 ms | 852 KB | Output is correct |
11 | Correct | 2 ms | 980 KB | Output is correct |
12 | Correct | 1 ms | 852 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 852 KB | Output is correct |
4 | Incorrect | 1 ms | 980 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 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 | 1 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 212 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
8 | Correct | 1 ms | 212 KB | Output is correct |
9 | Correct | 1 ms | 212 KB | Output is correct |
10 | Correct | 1 ms | 852 KB | Output is correct |
11 | Correct | 2 ms | 980 KB | Output is correct |
12 | Correct | 1 ms | 852 KB | Output is correct |
13 | Correct | 1 ms | 212 KB | Output is correct |
14 | Correct | 1 ms | 212 KB | Output is correct |
15 | Correct | 1 ms | 852 KB | Output is correct |
16 | Incorrect | 1 ms | 980 KB | Output isn't correct |
17 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 80 ms | 19540 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 80 ms | 19540 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |