Submission #782666

#	Time	Username	Problem	Language	Result	Execution time	Memory
782666		Lyrically	Sorting (IOI15_sorting)	C++17	100 / 100	142 ms	18800 KiB

sorting

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
int read(){int x;scanf("%d",&x);return x;}
void print(int x){printf("%d\n",x);}
const int mod=998244353;
int tp[600005],tq[600005];
int sr[600005];
int fa[600005];
bool vis[600005];
int to[600005],iv[600005];
bool check(int ps,int n,int m,int s[],int x[],int y[])
{
	int tot=0;
	rep(i,n){sr[i]=s[i];}
	rep(i,ps)
	{
		swap(sr[x[i]],sr[y[i]]);
	}
	rep(i,n)
	{
		fa[sr[i]]=i;vis[i]=0;
	}
	rep(i,n)
	{
		if(!vis[i])
		{
			int now=i;
			while(!vis[now])
			{
				vis[now]=1;
				if(vis[fa[now]]){break;}
				tp[tot]=now,tq[tot]=fa[now];tot++;
				now=fa[now];
			}
		}
	}
	if(tot>=ps+1){return 0;}
	for(int i=tot;i<m;i++){tp[i]=tq[i]=0;}
	return 1;
}
int findSwapPairs(int n,int s[],int m,int x[],int y[],int p[],int q[])
{
	if(is_sorted(s,s+n)){return 0;}
	int l=1,r=m;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(check(mid,n,m,s,x,y)){r=mid-1;}
		else{l=mid+1;}
	}
	check(l,n,m,s,x,y);
	rep(i,n){to[i]=iv[i]=i;}
	for(int i=l-1;i>=0;i--)
	{
		p[i]=to[tp[i]];q[i]=to[tq[i]];
		swap(iv[x[i]],iv[y[i]]);
		swap(to[iv[x[i]]],to[iv[y[i]]]);
	}
	return l;
}

Compilation message (stderr)

sorting.cpp: In function 'int read()':
sorting.cpp:7:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | int read(){int x;scanf("%d",&x);return x;}
      |                  ~~~~~^~~~~~~~~

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