Submission #672810

#	Time	Username	Problem	Language	Result	Execution time	Memory
672810		jamezzz	Sorting (IOI15_sorting)	C++17	100 / 100	302 ms	25232 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;

#define maxn 200005

int a[maxn],pos[maxn],plate[maxn];

int findSwapPairs(int N,int S[],int M,int X[],int Y[],int P[],int Q[]){
    int lo=0,hi=M,mid,res=0;
    while(lo<=hi){
		mid=(lo+hi)>>1;
		//printf("mid: %d\n",mid);
		for(int i=0;i<N;++i)plate[i]=i,a[i]=S[i];
		for(int i=mid-1;i>=0;--i)swap(plate[X[i]],plate[Y[i]]);
		for(int i=0;i<N;++i)pos[plate[i]]=i;
		//printf("pos: ");for(int i=0;i<N;++i)printf("%d ",pos[i]);printf("\n");
		//printf("plate: ");for(int i=0;i<N;++i)printf("%d ",plate[i]);printf("\n");
		vector<pair<int,int>> v;
		for(int i=0;i<N;++i){
			while(plate[i]!=a[i]){
				v.push_back({plate[i],a[i]});
				//printf("swap: %d %d\n",a[i],plate[i]);
				swap(a[i],a[pos[a[i]]]);
			}
		}
		if(v.size()<=mid){
			for(int i=0;i<v.size();++i){
				int a=plate[X[i]],b=plate[Y[i]];
				swap(pos[a],pos[b]);
				swap(plate[X[i]],plate[Y[i]]);
				auto[x,y]=v[i];
				P[i]=pos[x],Q[i]=pos[y];
				//printf("plate: ");for(int i=0;i<N;++i)printf("%d ",plate[i]);printf("\n");
				//printf("pos: ");for(int i=0;i<N;++i)printf("%d ",pos[i]);printf("\n");
			}
			for(int i=v.size();i<M;++i)P[i]=Q[i]=0;
			hi=mid-1;
			res=mid;
		}
		else lo=mid+1;
	}
	return res;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:27:14: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |   if(v.size()<=mid){
      |      ~~~~~~~~^~~~~
sorting.cpp:28:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |    for(int i=0;i<v.size();++i){
      |                ~^~~~~~~~~
sorting.cpp:29:9: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   29 |     int a=plate[X[i]],b=plate[Y[i]];
      |         ^
sorting.cpp:7:5: note: shadowed declaration is here
    7 | int a[maxn],pos[maxn],plate[maxn];
      |     ^
sorting.cpp:37:20: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   37 |    for(int i=v.size();i<M;++i)P[i]=Q[i]=0;
      |              ~~~~~~^~

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