oj.uz

Submission #742301

# Submission time Handle Problem Language Result Execution time Memory
742301 2023-05-16T05:11:00 Z fractlpaca Sorting (IOI15_sorting) C++17
8 / 100
 88 ms 38720 KB 
#include "sorting.h"

#include <vector>
#include <algorithm>
#include <utility>
// #include <iostream>

#define v vector
#define fi first
#define se second

using namespace std;

int n, m;
int *s, *x, *y, *p, *q;

v<v<int>> positions;

bool binary_search (int r) {
	v<int> reverse_positions (n, 0);
	for (int i=0; i<n; i++) {
		reverse_positions[positions[r][i]] = i;
	}
	v<pair<int,int>> pairs;
	v<int> working (n, 0);
	for (int i=0; i<n; i++) {
		working[i] = s[reverse_positions[i]];
	}
	v<int> swaps (n, 0);
	for (int i=0; i<n; i++) {
		swaps[i] = i;
	}
	
	int counter = 0;
	// for (int j=0; j<n; j++) cerr<<positions[r][j]<<" ";
	// cerr<<endl;
	// for (int j=0; j<n; j++) cerr<<working[j]<<" ";
	// cerr<<endl;
	for (int i=0; i<n-1; i++) {
		int mi = i;
		for (int j=i+1; j<n; j++) {
			if (working[j] < working[mi]) {
				mi = j;
			}
		}
		if (mi != i) {
			if (++counter > r) return false;
			// cerr<<"INFO "<<r<<" "<<counter<<" "<<i<<" "<<mi<<" "<<reverse_positions[swaps[i]]<<" "<<reverse_positions[swaps[mi]]<<endl;
			int i_d = swaps[positions[counter][reverse_positions[swaps[i]]]];
			int mi_d = swaps[positions[counter][reverse_positions[swaps[mi]]]];
			swap(swaps[i], swaps[mi]);
			swap(working[i], working[mi]);
			// for (int j=0; j<n; j++) cerr<<working[j]<<" ";
			// cerr<<endl;
			pairs.push_back({i_d, mi_d});
		}
	}
	for(int i=0; i<counter; i++) {
		p[i] = pairs[i].fi;
		q[i] = pairs[i].se;
	}
	for(int i=counter; i<r; i++) {
		p[i] = 0;
		q[i] = 0;
	}
	return true;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	n=N; s=S; m=M; x=X; y=Y; p=P; q=Q;
    positions = v<v<int>> (m+1, v<int> (n, 0));
	for (int i=0; i<n; i++) {
		positions[0][i] = i;
	}
	v<int> reverse_positions = positions[0];
	for(int r=1; r<=m; r++) {
		positions[r] = positions[r-1];
		swap(positions[r][reverse_positions[x[r-1]]], positions[r][reverse_positions[y[r-1]]]);
		swap(reverse_positions[x[r-1]], reverse_positions[y[r-1]]);
	}
	int l = -1, r = m;
	while (l+1 < r) {
		int mid = (l+r)/2;
		//cerr<<l<<" "<<r<<" "<<mid<<endl;
		if (binary_search(mid)) {
			r = mid;
		} else {
			l = mid;
		}
	}
	return r;
}

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
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 1 ms 212 KB Output is correct
10 Incorrect 1 ms 1492 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

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

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 1 ms 212 KB Output is correct
10 Incorrect 1 ms 1492 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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

Subtask #6
0 / 26.0

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