oj.uz

Submission #302417

# Submission time Handle Problem Language Result Execution time Memory
302417 2020-09-18T16:32:14 Z bensonlzl Sorting (IOI15_sorting) C++14
74 / 100
 48 ms 13176 KB 
#include "sorting.h"
#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pi;

int n, m, x[100005], y[100005], s[100005];

vector<pi> swaps;

bool sortable(int limit){
	//cerr << "STARTING " << limit << '\n';
	swaps.clear();
	vector<int> p(n), rev(n);
	vector<int>	fp(n);
	vector<int> vis(n,0);
	vector<pi> temp;
	for (int i = 0; i < n; ++i){
		p[i] = i;
	}
	for (int i = 0; i < limit; ++i){
		swap(p[x[i]],p[y[i]]);
	}
	for (int i = 0; i < n; ++i){
		fp[i] = s[p[i]];
	}
	for (int i = 0; i < n; ++i){
		if (!vis[i]){
			vis[i] = 1;
			int idx = fp[i];
			while (idx != i){
				vis[idx] = 1;
				temp.push_back(pi(idx,fp[idx]));
				idx = fp[idx];
			}
		}
	}
	if (temp.size() > limit) return false;
	while (temp.size() < limit) temp.push_back(pi(0,0));
	for (int i = 0; i < n; ++i){
		p[i] = s[i];
		rev[s[i]] = i;
	}
	for (int i = 0; i < limit; ++i){
		//cerr << x[i] << ' ' << y[i] << '\n';
		swap(rev[p[x[i]]],rev[p[y[i]]]);
		swap(p[x[i]],p[y[i]]);
		//for (auto it : p) cerr << it << ' ';
		//cerr << '\n';
		int s1 = rev[temp[i].first], s2 = rev[temp[i].second];
		//cerr << s1 << ' ' << s2 << '\n';
		swaps.push_back(pi(s1,s2));
		swap(rev[p[s1]],rev[p[s2]]);
		swap(p[s1],p[s2]);
		//for (auto it : p) cerr << it << ' ';
		//cerr << '\n';
	}
	return true;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	n = N;
	m = M;
	for (int i = 0; i < N; ++i){
		s[i] = S[i];
	}
	for (int i = 0; i < M; ++i){
		x[i] = X[i];
		y[i] = Y[i];
	}
	
    int ans = 0;
    if (sortable(0)) return 0;
    for (int i = 19; i >= 0; --i){
		int test = ans + (1 << i);
		if (test > M) continue;
		if (!sortable(test)) ans = test;
	}
	ans++;
	sortable(ans);
    for (int i = 0; i < ans; ++i){
		P[i] = swaps[i].first;
		Q[i] = swaps[i].second;
	}
	return ans;
}

Compilation message

sorting.cpp: In function 'bool sortable(int)':
sorting.cpp:39:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |  if (temp.size() > limit) return false;
      |      ~~~~~~~~~~~~^~~~~~~
sorting.cpp:40:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |  while (temp.size() < limit) temp.push_back(pi(0,0));
      |         ~~~~~~~~~~~~^~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 288 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 3 ms 896 KB Output is correct
22 Correct 2 ms 896 KB Output is correct
23 Correct 2 ms 896 KB Output is correct
24 Correct 3 ms 896 KB Output is correct
25 Correct 2 ms 896 KB Output is correct
26 Correct 2 ms 896 KB Output is correct
27 Correct 2 ms 896 KB Output is correct

Subtask #5
20.0 / 20.0

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

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 3 ms 640 KB Output is correct
12 Correct 2 ms 640 KB Output is correct
13 Correct 2 ms 640 KB Output is correct
14 Correct 2 ms 640 KB Output is correct
15 Runtime error 48 ms 13176 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -