oj.uz

Submission #329186

# Submission time Handle Problem Language Result Execution time Memory
329186 2020-11-19T16:12:27 Z arnold518 Sorting (IOI15_sorting) C++14
0 / 100
 2 ms 620 KB 
#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 6e5;

int N, M, ans;
int S[MAXN+10], X[MAXN+10], Y[MAXN+10], *P, *Q;
int A[MAXN+10], B[MAXN+10], T[MAXN+10];
bool vis[MAXN+10];

bool solve(int R)
{	
	for(int i=1; i<=N; i++) A[i]=S[i];
	for(int i=1; i<=R; i++)
	{
		swap(A[X[i]], A[Y[i]]);
	}

	vector<pii> V;
	for(int i=1; i<=N; i++) vis[i]=false;

	//for(int i=1; i<=N; i++) printf("%d ", A[i]); printf("\n");
	for(int i=1; i<=N; i++)
	{
		if(vis[i]) continue;
		for(int now=i; ; now=A[now])
		{
			vis[now]=true;
			if(vis[A[now]]) break;
			V.push_back({A[now], A[A[now]]});
			//printf("!%d %d\n", A[now], A[A[now]]);
		}
	}
	if(V.size()>R) return false;

	for(int i=1; i<=N; i++) T[i]=i, A[i]=i;
	for(int i=1; i<=R; i++) P[i]=Q[i]=1;
	for(int i=R; i>=1; i--)
	{
		//for(int j=1; j<=N; j++) printf("%d ", A[j]); printf("\n");
		if(!V.empty())
		{
			pii t=V.back(); V.pop_back();
			pii a=pii(T[t.first], T[t.second]);
			P[i]=a.first; Q[i]=a.second;
			swap(A[a.first], A[a.second]);
			swap(T[t.first], T[t.second]);
		}

		//for(int j=1; j<=N; j++) printf("%d ", A[j]); printf("\n");

		pii a=pii(X[i], Y[i]);
		pii t=pii(A[a.first], A[a.second]);
		swap(A[a.first], A[a.second]);
		swap(T[t.first], T[t.second]);
	}
	//for(int j=1; j<=N; j++) printf("%d ", A[j]); printf("\n");

	for(int i=0; i<R; i++)
	{
		P[i]=P[i+1]-1;
		Q[i]=Q[i+1]-1;
	}
	return true;
}

int findSwapPairs(int _N, int _S[], int _M, int _X[], int _Y[], int _P[], int _Q[])
{
	N=_N; M=_M; P=_P; Q=_Q;
	for(int i=1; i<=N; i++) S[i]=_S[i-1]+1;
	for(int i=1; i<=M; i++) X[i]=_X[i-1]+1, Y[i]=_Y[i-1]+1;

	int lo=0, hi=M;
	while(lo+1<hi)
	{
		int mid=lo+hi>>1;
		if(solve(mid)) hi=mid;
		else lo=mid;
	}
	for(int i=0; i<hi; i++)
	{
		swap(_S[_X[i]], _S[_Y[i]]);
		swap(_S[Q[i]], _S[P[i]]);
	}
	//for(int i=0; i<N; i++) printf("%d ", _S[i]);
	for(int i=0; i<N; i++) assert(i==_S[i]);
	return hi;
}

Compilation message

sorting.cpp: In function 'bool solve(int)':
sorting.cpp:39:13: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |  if(V.size()>R) return false;
      |     ~~~~~~~~^~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:81:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |   int mid=lo+hi>>1;
      |           ~~^~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 2 ms 620 KB Output is correct
4 Incorrect 1 ms 620 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 2 ms 620 KB Output is correct
4 Incorrect 1 ms 620 KB Output isn't correct
5 Halted 0 ms 0 KB -