oj.uz

Submission #16563

# Submission time Handle Problem Language Result Execution time Memory
16563 2015-08-28T04:11:05 Z gs14004 Sorting (IOI15_sorting) C++14
0 / 100
 3 ms 384 KB 
#include "sorting.h"
#include <algorithm>
using namespace std;

int *s, *x, *y, *p, *q, n;
int obj[200005], cur[200005];
int orev[200005], crev[200005];

bool trial(int t){
	for(int i=0; i<n; i++){
		obj[i] = i;
		cur[i] = s[i];
		crev[s[i]] = i;
	}
	for(int i=t-1; i>=0; i--){
		swap(obj[x[i]], obj[y[i]]);
		orev[obj[x[i]]] = x[i];
		orev[obj[y[i]]] = y[i];
	}
	int pt = 0;
	for(int i=0; i<t; i++){
		swap(obj[x[i]], obj[y[i]]);
		swap(cur[x[i]], cur[y[i]]);
		crev[cur[x[i]]] = x[i];
		orev[obj[x[i]]] = x[i];
		crev[cur[y[i]]] = y[i];
		orev[obj[y[i]]] = y[i];
		while(pt < n && crev[pt] == orev[pt]) pt++;
		if(pt == n){
			p[i] = q[i] = 0;
			continue;
		}
		int p1 = crev[pt];
		int p2 = orev[pt];
		p[i] = p1;
		q[i] = p2;
		swap(cur[p1], cur[p2]);
		crev[cur[p1]] = p1;
		crev[cur[p2]] = p2;
	}
	while(pt < n && crev[pt] == orev[pt]) pt++;
	return (pt == n);
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	n = N, s = S, x = X, y = Y, p = P, q = Q;
	int s = 0, e = min(N, M);
	while(s != e){
		int m = (s+e)/2;
		if(trial(m)) e = m;
		else s = m+1;
	}
	trial(s);
	return s;
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:47:6: warning: declaration of 's' shadows a global declaration [-Wshadow]
  int s = 0, e = min(N, M);
      ^
sorting.cpp:5:6: note: shadowed declaration is here
 int *s, *x, *y, *p, *q, n;
      ^

Subtask #1
0 / 8.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB Output is correct
2 Incorrect 3 ms 324 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 256 KB Output is correct
2 Incorrect 2 ms 256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 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 384 KB Output isn't correct
2 Halted 0 ms 0 KB -