Submission #1030447

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030447		pcc	Sorting (IOI15_sorting)	C++17	100 / 100	211 ms	34540 KiB

sorting

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

#define pii pair<int,int>
#define fs first
#define sc second

const int mxn = 6e5+10;
pii arr[mxn];
int N,M;
int done = 0;
bitset<mxn> vis;
vector<pii> ans;

void act(vector<int> &perm,vector<int> &pos,int a,int b){
	//cerr<<"ACT "<<a<<','<<b<<endl;
	//cerr<<"PERM: ";for(auto &i:perm)cerr<<i<<' ';cerr<<endl;
	//cerr<<"POS: ";for(auto &i:pos)cerr<<i<<' ';cerr<<endl;
	swap(perm[a],perm[b]);
	swap(pos[perm[a]],pos[perm[b]]);
	//cerr<<"ACTED"<<a<<','<<b<<endl;
	//cerr<<"PERM: ";for(auto &i:perm)cerr<<i<<' ';cerr<<endl;
	//cerr<<"POS: ";for(auto &i:pos)cerr<<i<<' ';cerr<<endl;
	return;
}

bool f(int len,vector<int> perm){
	//cerr<<"----------------------------------------"<<endl;
	//cerr<<"F "<<len<<" start!"<<endl;
	vis.reset();
	ans.clear();
	vector<int> pos(N);
	for(int i = 0;i<N;i++)pos[perm[i]] = i;

	auto v = perm;
	for(int i = 0;i<len;i++){
		auto [a,b] = arr[i];
		swap(v[a],v[b]);
	}
	auto p = v;
	for(int i = 0;i<N;i++){
		p[v[i]] = v[v[i]];
	}
	vector<pii> need;
	for(int i = 0;i<N;i++){
		int now = i;
		vis[now] = true;
		while(!vis[p[now]]){
			need.push_back(pii(now,p[now]));
			now = p[now];
			vis[now] = true;
		}
	}
	for(auto &i:v)//cerr<<i<<' ';cerr<<endl;
	//cerr<<"NEED: "<<endl;for(auto &i:need)cerr<<i.fs<<' '<<i.sc<<endl;cerr<<endl;
	if(need.size()>len)return false;
	while(need.size()<len)need.push_back(pii(0,0));
	for(int i = 0;i<len;i++){
		auto [a,b] = arr[i];
		act(perm,pos,a,b);
		auto [c,d] = need[i];
		ans.push_back(pii(pos[c],pos[d]));
		act(perm,pos,pos[c],pos[d]);
	}
	for(int i = 0;i<N;i++)assert(perm[i] == i);
	//cerr<<"----------------------------------------"<<endl;
	return true;
}

void construct(int P[],int Q[],int len){
	if(ans.size() != len)exit(0);
	assert(ans.size() == len);
	for(int i = 0;i<len;i++){
		P[i] = ans[i].fs,Q[i] = ans[i].sc;
	}
	return;
}

int findSwapPairs(int NN, int S[], int MM, int X[], int Y[], int P[], int Q[]) {
	N = NN;M = MM;
	for(int i = 0;i<M;i++)P[i] = Q[i] = 0;
	vector<int> v(N);
	for(int i = 0;i<N;i++){
		v[i] = S[i];
	}
	for(int i = 0;i<M;i++)arr[i] = pii(X[i],Y[i]);
	//cerr<<"INIT!"<<endl;
	int l = 0,r = N;
	while(l != r){
		int mid = (l+r)>>1;
		if(f(mid,v))r = mid;
		else l = mid+1;
	}
	assert(f(l,v));
	construct(P,Q,l);
	return l;
	return -1;
	assert(false);
}

Compilation message (stderr)

sorting.cpp: In function 'bool f(int, std::vector<int>)':
sorting.cpp:57:16: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |  if(need.size()>len)return false;
      |     ~~~~~~~~~~~^~~~
sorting.cpp:55:12: warning: unused variable 'i' [-Wunused-variable]
   55 |  for(auto &i:v)//cerr<<i<<' ';cerr<<endl;
      |            ^
sorting.cpp:58:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |  while(need.size()<len)need.push_back(pii(0,0));
      |        ~~~~~~~~~~~^~~~
sorting.cpp: In function 'void construct(int*, int*, int)':
sorting.cpp:72:16: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |  if(ans.size() != len)exit(0);
      |     ~~~~~~~~~~~^~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from sorting.cpp:2:
sorting.cpp:73:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   73 |  assert(ans.size() == len);
      |         ~~~~~~~~~~~^~~~~~

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