oj.uz

Submission #758522

# Submission time Handle Problem Language Result Execution time Memory
758522 2023-06-14T18:24:59 Z APROHACK Sorting (IOI15_sorting) C++14
36 / 100
 3 ms 724 KB 
#include "sorting.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define ff first
#define ss second
using namespace std;


void cambiar(vector<int>&v, int i, int j){
	int temp = v[i];
	v[i] = v[j];
	v[j] = temp;
}
int buenos;
bool sorted(int n){
	return buenos == n;
}

int test(int N, vector<int>&S, int M, vector<int>&X, vector<int>&Y, vector<int>&P, vector<int>&Q){
	vector<int>arr;
	vector<int>whereIs[2];
	vector<int>current;
	
	buenos = 0;
	vector<int>copia;
	bool valid = true;
	for(int i = 0 ; i < N ; i ++){
		whereIs[0].pb(0);
		whereIs[1].pb(0);
		if(S[i] != i)valid = false;
	}
	if(valid)return 0;
	for(int i = 0 ; i < N ; i ++){
		copia.pb(S[i]);
		current.pb(S[i]);
		arr.pb(S[i]);
		whereIs[0][S[i]] = i;
		whereIs[1][S[i]] = i;
		
		if(current[i] == i)buenos ++;
	}
	for(int i = 0 ; i < M ; i ++){
		cambiar(copia, X[i], Y[i]);
		//for(auto j : copia) cout << j << " " ;
		//cout << endl;
	}
	for(int i = 0 ; i < N ; i ++){
		//cout << "donde esta " << copia[i] << " = " << whereIs[copia[i]] << endl;
		arr[whereIs[0][copia[i]]] = i;
	}
	for(int i  = 0 ; i < N ; i ++){
		whereIs[0][arr[i]] = i;
	}
	int currentC = 0, movimientos = 0;
	int i = 0;
	int temporal, t2;
	while(i < M){
		//for(auto k : current)cout << k << " ";
		//cout << endl;
		if(sorted(N))return movimientos;
		cambiar(arr, X[i], Y[i]);
		whereIs[0][arr[X[i]]] = X[i];
		whereIs[0][arr[Y[i]]] = Y[i];
		
		temporal = 0, t2 = 0;
		if(current[X[i]] == X[i])temporal ++;
		if(current[Y[i]] == Y[i])temporal ++;
		cambiar(current, X[i], Y[i]);
		if(current[X[i]] == X[i])t2 ++;
		if(current[Y[i]] == Y[i])t2 ++;
		buenos += t2-temporal;
		whereIs[1][current[X[i]]] = X[i];
		whereIs[1][current[Y[i]]] = Y[i];
		while(currentC < N and whereIs[1][currentC] == whereIs[0][currentC])currentC++;
		if(currentC < N){
			P[i] = whereIs[1][currentC];
			Q[i] = whereIs[0][currentC];
			temporal = 0;
			t2  = 0;
			if(current[P[i]] == P[i])temporal ++;
			if(current[Q[i]] == Q[i])temporal ++;
			cambiar(current, P[i], Q[i]);
			if(current[P[i]] == P[i])t2 ++;
			if(current[Q[i]] == Q[i])t2 ++;
			buenos += t2-temporal;
			whereIs[1][current[P[i]]] = P[i];
			whereIs[1][current[Q[i]]] = Q[i];
			i++;
			currentC++;
			movimientos++;
		}else{
			i++;
			currentC++;
			movimientos++;
		}
	}
	
	//for(auto k : current)cout << k << " ";
	if(sorted(N))return movimientos;
	else return -1;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	vector<int>s, x, y, p, q;
	for(int i = 0 ; i < N ; i ++){
		s.pb(S[i]);
	}
	for(int i = 0 ; i < M ; i ++){
		x.pb(X[i]);
		y.pb(Y[i]);
		p.pb(0);
		q.pb(0);
	}
	int ans;
	int li = 0, ls = N, pos;
	pos = (li + ls)/2;
	while(li + 1 < ls){
		ans = test(N, s, pos, x, y, p, q);
		if(ans == -1){
			li = pos+1;
		}else{
			ls = pos;
		}
		pos = (li + ls)/2;
	}
	ans = test(N, s, li, x, y, p, q);
	if(ans == -1)ans = test(N, s, li+1, x, y, p, q);
	for(int i = 0 ; i < ans ; i ++){
		P[i] = p[i];
		Q[i] = q[i];
	}
	return ans;
	
}

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 2 ms 724 KB Output is correct
22 Incorrect 2 ms 724 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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

Subtask #6
0 / 26.0

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