Submission #241858

#	Time	Username	Problem	Language	Result	Execution time	Memory
241858		Nightlight	Sorting (IOI15_sorting)	C++14	20 / 100	6 ms	512 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;

int N, M;
int pos[200005];
int S[200005], A[200005];
int X[600005], Y[600005];
int P[600005], Q[600005];
int pp;
bool qq;
void balance(int now) {
	while(pp <= now) swap(S[X[pp]], S[Y[pp]]), pp++;
	while(pp > now + 1) swap(S[X[pp - 1]], S[Y[pp - 1]]), pp--;
}

bool trysort(int limit) {
	int cnt = 0;
//	cout << limit << "\n";
	for(int i = 0; i < N; i++) {
		A[i] = S[i];
//		cout << A[i] << " ";
		pos[A[i]] = i;
	}
//	cout << "\n";
	for(int i = 0; i < N; i++) {
		if(A[i] != i) {
			P[cnt] = i, Q[cnt] = pos[i];
			cnt++;
			int b = A[i];
			swap(A[i], A[pos[i]]);
			pos[b] = pos[i];
			pos[i] = i;
//			if(qq)for(int j = 0; j < N; j++) cout << A[j] << " ";
//			if(qq)cout << "\n";
		}
	}
	for(int i = cnt; i < limit; i++) {
		P[i] = 0, Q[i] = 0;
	}
//	cout << cnt << "\n\n";
	return cnt <= limit;
}

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 = 1; i <= M; i++) X[i] = x[i - 1], Y[i] = y[i - 1];
	int l = 0, r = M, res = 0;
	while(l <= r) {
		int mid = (l + r) >> 1;
		balance(mid);
		if(trysort(mid)) {
			res = mid;
			r = mid - 1;
		}else l = mid + 1;
	}
	balance(res);
	qq = 1;
	trysort(res);
	for(int i = 0; i < res; i++) {
		p[i] = P[i], q[i] = Q[i];
	}
	system("pause");
	return res;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:64:8: warning: ignoring return value of 'int system(const char*)', declared with attribute warn_unused_result [-Wunused-result]
  system("pause");
  ~~~~~~^~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 0 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 20
• Subtask 6: 0 / 26