oj.uz

Submission #58551

# Submission time Handle Problem Language Result Execution time Memory
58551 2018-07-18T06:47:13 Z ngkan146 Sorting (IOI15_sorting) C++11
0 / 100
 3 ms 512 KB 
#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
int n;
int a[200000], b[200000];
int m;
int x[600000], y[600000];
bool check(int val){
	for(int i=0;i<n;i++)
		b[i] = a[i];
		
	for(int i=0;i<val;i++)
		swap(b[x[i]], b[y[i]]);
		
	int cnt = n;
	for(int i=0;i<n;i++){
		if (b[i] == -1)	continue;
		cnt--;
		int index = i;
		do{
			int nex = b[index];
			b[index] = -1;
			index = nex;
		}while(index != i);
	}
	
	return cnt <= val;
}
int trace(int val,int P[], int Q[]){
	for(int i=0;i<n;i++)
		b[i] = a[i];
		
	for(int i=0;i<val;i++)
		swap(b[x[i]], b[y[i]]);
		
	int cnt = 0;
	for(int i=0;i<n;i++){
		if (b[i] == -1)	continue;
		cnt--;
		int index = i;
		for(int _=0;b[index] != -1;_++){
			int nex = b[index];
			b[index] = -1;
			if (_){
				P[cnt] = index;
				Q[cnt] = nex;
				++cnt;
			}
			index = nex;
		}
	}
	
	while(cnt < val)	P[cnt] = Q[cnt] = 0, ++cnt;
	return val;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	n = N;
	for(int i=0;i<n;i++)
		a[i] = S[i];
	m = M;
	for(int i=0;i<m;i++)
		x[i] = X[i],
		y[i] = Y[i];
	
	int l=-1, r=m;
	while(l+1<r){
		int mid = (l+r)/2;
		if (check(mid))	r = mid;
		else l = mid;
	}
	return trace(r,P,Q);
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 20.0

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

Subtask #6
0 / 26.0

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