Submission #1025365

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025365		boyliguanhan	Sorting (IOI15_sorting)	C++17	100 / 100	143 ms	22800 KiB

sorting

#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;
}

Compilation message (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;
      |          ^

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 20 / 20
• Subtask 6: 26 / 26