Submission #1036482

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036482		vjudge1	Sorting (IOI15_sorting)	C++17	54 / 100	46 ms	59516 KiB

sorting

#include "sorting.h"

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

using pii=pair<int,int>;

#define pb push_back

const int lim=2e5+100;
int n,m,*s,*x,*y,*p,*q;

struct rollbackdsu{
	int par[lim],sz[lim];
	int compcnt,opcnt;
	struct opr{
		int id,i,j;
	};
	stack<opr>ops;
	void init(){
		for(int i=0;i<n;i++){
			par[i]=i;
			sz[i]=1;
		}
		compcnt=n,opcnt=0;
	}
	int find(int i){
		while(i!=par[i]){
			i=par[i];
		}
		return i;
	}
	void unite(int i,int j){
		i=find(i),j=find(j);
		if(i^j){
			if(sz[i]<sz[j])swap(i,j);
			ops.push({opcnt,i,j});
			par[j]=i;
			sz[i]+=sz[j];
			compcnt--;
		}
		opcnt++;
	}
	void rollback(){
		opcnt--;
		if(ops.size()&&ops.top().id==opcnt){
			auto[id,i,j]=ops.top();
			sz[i]-=sz[j];
			par[j]=j;
			ops.pop();
			compcnt++;
		}
	}
};

struct{
	rollbackdsu dsu;
	vector<pii>tree[12*lim];
	map<pii,int>edgetrack;
	int tm=0;
	void init(){
		dsu.init();
	}
	int L,R;
	pii VAL;
	void update(int l,int r,int node){
		if(L<=l&&r<=R){
			tree[node].pb(VAL);
			return;
		}
		if(r<L||R<l)return;
		int mid=(l+r)>>1,child=node<<1;
		update(l,mid,child),update(mid+1,r,child|1);
	}
	void update(int l,int r,pii val){
		L=l,R=r,VAL=val;
		update(0,m,1);
	}
	void addedge(pii val){
		edgetrack[val]=tm;
	}
	void removeedge(pii val){
		int past=edgetrack[val];
		edgetrack.erase(val);
		update(past,tm-1,val);
	}
	void passtime(){tm++;}
	void roll(int node){
		for(auto[x,y]:tree[node]){
			dsu.rollback();
		}
	}
	int walk(int l,int r,int node){
		for(auto[x,y]:tree[node]){
			dsu.unite(x,y);
		}
		if(l==r){
			if(n-dsu.compcnt<=l){
				roll(node);
				return l;
			}
			roll(node);
			return -1;
		}
		int mid=(l+r)>>1,child=node<<1;
		int leftval=walk(l,mid,child),rightval=walk(mid+1,r,child|1);
		roll(node);
		if(leftval!=-1)return leftval;
		return rightval;
	}
	int walk(){
		assert(tm==m+1);
		for(auto[x,y]:edgetrack){
			update(y,m,x);
		}
		return walk(0,m,1);
	}
}dsu;

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	n=N,m=M,s=S,x=X,y=Y,p=P,q=Q;
	dsu.init();
	for(int i=0;i<n;i++){
		dsu.addedge({i,s[i]});
	}
	dsu.passtime();
	int a[n];
	for(int i=0;i<n;i++){
		a[i]=s[i];
	}
	for(int i=0;i<m;i++){
		dsu.removeedge({x[i],a[x[i]]});
		dsu.removeedge({y[i],a[y[i]]});
		swap(a[x[i]],a[y[i]]);
		dsu.addedge({x[i],a[x[i]]});
		dsu.addedge({y[i],a[y[i]]});
		dsu.passtime();
	}
	int res=dsu.walk();
	for(int i=0;i<n;i++){
		a[i]=s[i];
	}
	for(int i=0;i<res;i++){
		swap(a[x[i]],a[y[i]]);
	}
	int pos[n];
	for(int i=0;i<n;i++){
		pos[s[i]]=i;
	}
	int j=0;
	for(int i=0;i<res;i++){
		swap(s[x[i]],s[y[i]]);
		pos[s[x[i]]]=x[i];
		pos[s[y[i]]]=y[i];
		while(j<n&&a[j]==j)j++;
		if(j==n)p[j]=q[j]=0;
		else{
			p[i]=pos[a[j]];
			q[i]=pos[a[a[j]]];
			swap(s[p[i]],s[q[i]]);
			pos[s[p[i]]]=p[i];
			pos[s[q[i]]]=q[i];
			swap(a[j],a[a[j]]);
		}
	}
	return res;
}

Compilation message (stderr)

sorting.cpp: In member function 'void<unnamed struct>::roll(int)':
sorting.cpp:89:12: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   89 |   for(auto[x,y]:tree[node]){
      |            ^
sorting.cpp:11:13: note: shadowed declaration is here
   11 | int n,m,*s,*x,*y,*p,*q;
      |             ^
sorting.cpp:89:14: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   89 |   for(auto[x,y]:tree[node]){
      |              ^
sorting.cpp:11:16: note: shadowed declaration is here
   11 | int n,m,*s,*x,*y,*p,*q;
      |                ^
sorting.cpp:89:11: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
   89 |   for(auto[x,y]:tree[node]){
      |           ^~~~~
sorting.cpp: In member function 'int<unnamed struct>::walk(int, int, int)':
sorting.cpp:94:12: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   94 |   for(auto[x,y]:tree[node]){
      |            ^
sorting.cpp:11:13: note: shadowed declaration is here
   11 | int n,m,*s,*x,*y,*p,*q;
      |             ^
sorting.cpp:94:14: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   94 |   for(auto[x,y]:tree[node]){
      |              ^
sorting.cpp:11:16: note: shadowed declaration is here
   11 | int n,m,*s,*x,*y,*p,*q;
      |                ^
sorting.cpp: In member function 'int<unnamed struct>::walk()':
sorting.cpp:113:12: warning: declaration of 'x' shadows a global declaration [-Wshadow]
  113 |   for(auto[x,y]:edgetrack){
      |            ^
sorting.cpp:11:13: note: shadowed declaration is here
   11 | int n,m,*s,*x,*y,*p,*q;
      |             ^
sorting.cpp:113:14: warning: declaration of 'y' shadows a global declaration [-Wshadow]
  113 |   for(auto[x,y]:edgetrack){
      |              ^
sorting.cpp:11:16: note: shadowed declaration is here
   11 | int n,m,*s,*x,*y,*p,*q;
      |                ^

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