oj.uz

Submission #387303

# Submission time Handle Problem Language Result Execution time Memory
387303 2021-04-08T08:56:00 Z alishahali1382 Sorting (IOI15_sorting) C++14
20 / 100
 4 ms 1004 KB 
#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define debug2(x, y) {cerr<<#x<<", "<<#y<<" = "<<x<<", "<<y<<"\n";}
#define pb push_back
#define all(x) x.begin(), x.end()

const int MAXN=200010, LOG=18;

int n, m, ans;
int A[MAXN], B[MAXN], C[MAXN], D[MAXN];
int posB[MAXN], posC[MAXN], posD[MAXN];
int X[MAXN], Y[MAXN], P[MAXN], Q[MAXN];

int Solve(int k){
	for (int i=0; i<n; i++){
		B[i]=A[i];
		C[i]=A[i];
		D[A[i]]=A[i];
	}
	for (int i=0; i<k; i++){
		swap(B[X[i]], B[Y[i]]);
		// swap(C[X[i]], C[Y[i]]);
	}
	for (int i=0; i<n; i++){
		posB[B[i]]=i;
		posC[C[i]]=i;
		posD[D[i]]=i;
	}
	int t=0;
	for (int i=0; i<n; i++) if (B[i]!=i){
		if (t==k) return 0;
		swap(C[X[t]], C[Y[t]]);
		swap(posC[C[X[t]]], posC[C[Y[t]]]);
		// cerr<<"C: ";for (int j=0; j<n; j++) cerr<<C[j]<<" \n"[j==n-1];
		// cerr<<"posC: ";for (int j=0; j<n; j++) cerr<<posC[j]<<" \n"[j==n-1];
		
		int x=i, y=B[i];
		// debug2(x, y)
		// debug2(D[x], D[y])
		// debug2(posC[D[x]], posC[D[y]])
		// cerr<<"\n";

		swap(D[x], D[y]);
		swap(B[posB[x]], B[posB[y]]);
		swap(posB[x], posB[y]);
		x=D[x];
		y=D[y];
		P[t]=posC[x];
		Q[t]=posC[y];
		t++;
	}
	return 1;
}

int findSwapPairs(int _n, int _A[], int _m, int _X[], int _Y[], int _P[], int _Q[]){
	n=_n;
	for (int i=0; i<n; i++) A[i]=_A[i];
	m=_m;
	for (int i=0; i<m; i++) X[i]=_X[i], Y[i]=_Y[i];
	
	int dwn=-1, up=m;
	while (up-dwn>1){
		int mid=(dwn+up)>>1;
		if (Solve(mid)) up=mid;
		else dwn=mid;
	}
	ans=up;
	Solve(ans);
	for (int i=0; i<ans; i++) _P[i]=P[i], _Q[i]=Q[i];
	
	for (int i=0; i<ans; i++){
		swap(A[X[i]], A[Y[i]]);
		swap(A[P[i]], A[Q[i]]);
	}
	for (int i=0; i<n; i++) assert(A[i]==i);
	return ans;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 2 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Runtime error 2 ms 620 KB Execution killed with signal 6

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 2 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 2 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Runtime error 2 ms 620 KB Execution killed with signal 6

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 620 KB Output is correct
2 Correct 3 ms 620 KB Output is correct
3 Runtime error 4 ms 1004 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 620 KB Output is correct
2 Correct 3 ms 620 KB Output is correct
3 Runtime error 4 ms 1004 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -