제출 #1098447

#제출 시각아이디문제언어결과실행 시간메모리
1098447alexander707070정렬하기 (IOI15_sorting)C++14
100 / 100
240 ms21952 KiB
#include<bits/stdc++.h> #include "sorting.h" #define MAXN 200007 using namespace std; int n,m,q,br; int pos[MAXN],s[MAXN],post[MAXN]; int to[MAXN]; int check(int stop, int S[], int X[], int Y[], int P[], int Q[]){ for(int i=0;i<n;i++)s[i]=i; for(int i=0;i<stop;i++)swap(s[X[i]],s[Y[i]]); for(int i=0;i<n;i++)to[s[i]]=i; for(int i=0;i<n;i++){ s[i]=S[i]; pos[s[i]]=i; post[to[i]]=i; } int pt=0; for(int i=0;i<stop;i++){ P[i]=Q[i]=0; swap(s[X[i]],s[Y[i]]); swap(to[X[i]],to[Y[i]]); swap(pos[s[X[i]]],pos[s[Y[i]]]); swap(post[to[X[i]]],post[to[Y[i]]]); while(pt<n and to[pos[pt]]==pt)pt++; if(pt==n)continue; P[i]=pos[pt]; Q[i]=post[pt]; swap(s[P[i]],s[Q[i]]); swap(pos[s[P[i]]],pos[s[Q[i]]]); } q=stop; br=0; for(int i=0;i<n;i++){ s[i]=S[i]; if(s[i]==i)br++; } for(int i=0;i<stop;i++){ if(br==n)return i; if(s[X[i]]==X[i])br--; if(s[Y[i]]==Y[i])br--; swap(s[X[i]],s[Y[i]]); if(s[X[i]]==X[i])br++; if(s[Y[i]]==Y[i])br++; if(s[P[i]]==P[i])br--; if(s[Q[i]]==Q[i])br--; swap(s[P[i]],s[Q[i]]); if(s[P[i]]==P[i])br++; if(s[Q[i]]==Q[i])br++; } if(br==n)return q; return -1; } int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { n=N; m=M; int l=-1,r=n,tt; while(l+1<r){ int tt=(l+r)/2; if(check(tt,S,X,Y,P,Q)!=-1){ r=tt; }else{ l=tt; } } return check(r,S,X,Y,P,Q); }

컴파일 시 표준 에러 (stderr) 메시지

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:78:7: warning: declaration of 'tt' shadows a previous local [-Wshadow]
   78 |   int tt=(l+r)/2;
      |       ^~
sorting.cpp:76:15: note: shadowed declaration is here
   76 |  int l=-1,r=n,tt;
      |               ^~
sorting.cpp:76:15: warning: unused variable 'tt' [-Wunused-variable]
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...