Submission #241861

#	Time	Username	Problem	Language	Result	Execution time	Memory
241861		Nightlight	Sorting (IOI15_sorting)	C++14	20 / 100	6 ms	624 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 SA[600005], SB[600005];
int res;
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--;
}

void SWAP(int i, int j) {
  int ii = pos[A[i]];
  int jj = pos[A[j]];
  pos[A[i]] = jj;
  pos[A[j]] = ii;
  swap(A[i], A[j]);
}

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) {
			SA[cnt] = i, SB[cnt] = A[i];
			cnt++;
			SWAP(i, pos[i]);
//			if(qq)for(int j = 0; j < N; j++) cout << A[j] << " ";
//      if(qq)cout << "\n";
		}
	}
	for(int i = cnt; i < limit; i++) {
		SA[i] = 0, SB[i] = 0;
	}
//	cout << cnt << "\n\n";
	return cnt <= limit;
}

void findans() {
  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 < res; i++) {
    SWAP(X[i], Y[i]);
    P[i] = pos[SA[i]], Q[i] = pos[SB[i]];
    SWAP(P[i], Q[i]);
  }
}

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;
  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);
  findans();
	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:86:9: 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