제출 #1025365

#제출 시각아이디문제언어결과실행 시간메모리
1025365boyliguanhan정렬하기 (IOI15_sorting)C++17
100 / 100
143 ms22800 KiB
#include "sorting.h" #include<bits/stdc++.h> using namespace std; bitset<200100>vis; int howmanydoineed(vector<int>v){ int n=v.size(),ans=n; for(int i=0;i<n;i++) if(!vis[i]){ ans--; int k=i; do { vis[k]=1; k=v[k]; }while(k-i); } vis.reset(); return ans; } vector<pair<int,int>>SWP; void getswaps(vector<int>v){ int n=v.size(); for(int i=0;i<n;i++) if(!vis[i]){ int k=i,VL=v[i]; do { SWP.push_back({VL,v[v[k]]}); VL=v[v[k]]; vis[k]=1; k=v[k]; }while(k-i); SWP.pop_back(); } vis.reset(); } bool docheck(int N,int k,int S[],int X[],int Y[]){ vector<int>v(N); for(int i=0;i<N;i++) v[i]=S[i]; for(int i=0;i<k;i++) swap(v[X[i]],v[Y[i]]); return howmanydoineed(v)<=k; } void docheck2(int N,int k,int S[],int X[],int Y[]){ vector<int>v(N); for(int i=0;i<N;i++) v[i]=S[i]; for(int i=0;i<k;i++) swap(v[X[i]],v[Y[i]]); getswaps(v); if(SWP.size()<k) SWP.push_back({0,0}); } vector<int>vals; vector<int>pos; int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { int l=0,r=M,res=1e9; while(l<=r){ int mid=l+r>>1; if(docheck(N,mid,S,X,Y)) r=mid-1,res=mid; else l=mid+1; } docheck2(N,res,S,X,Y); pos.resize(N); vals.resize(N); for(int i=0;i<N;i++) vals[i]=S[i],pos[S[i]]=i; int k=0; for(auto[x,y]:SWP){ int ermx=X[k],ermy=Y[k]; int K=vals[ermx],M=vals[ermy]; swap(vals[ermx],vals[ermy]); swap(pos[K],pos[M]); int l=pos[x],r=pos[y]; P[k]=l,Q[k++]=r; swap(vals[l],vals[r]); swap(pos[x],pos[y]); } return res; }

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

sorting.cpp: In function 'int howmanydoineed(std::vector<int>)':
sorting.cpp:6:17: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
    6 |     int n=v.size(),ans=n;
      |           ~~~~~~^~
sorting.cpp: In function 'void getswaps(std::vector<int>)':
sorting.cpp:21:14: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   21 |  int n=v.size();
      |        ~~~~~~^~
sorting.cpp: In function 'void docheck2(int, int, int*, int*, int*)':
sorting.cpp:50:15: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |  if(SWP.size()<k)
      |     ~~~~~~~~~~^~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:58:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |   int mid=l+r>>1;
      |           ~^~
sorting.cpp:71:20: warning: declaration of 'int M' shadows a parameter [-Wshadow]
   71 |   int K=vals[ermx],M=vals[ermy];
      |                    ^
sorting.cpp:55:39: note: shadowed declaration is here
   55 | int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
      |                                   ~~~~^
sorting.cpp:74:7: warning: declaration of 'l' shadows a previous local [-Wshadow]
   74 |   int l=pos[x],r=pos[y];
      |       ^
sorting.cpp:56:6: note: shadowed declaration is here
   56 |  int l=0,r=M,res=1e9;
      |      ^
sorting.cpp:74:16: warning: declaration of 'r' shadows a previous local [-Wshadow]
   74 |   int l=pos[x],r=pos[y];
      |                ^
sorting.cpp:56:10: note: shadowed declaration is here
   56 |  int l=0,r=M,res=1e9;
      |          ^
#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...