Submission #96892

#	Time	Username	Problem	Language	Result	Execution time	Memory
96892		figter001	Sorting (IOI15_sorting)	C++14	20 / 100	3 ms	512 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 2e5+50;

vector<int> a;
vector<pair<int,int>> s;
int idx[maxn];

bool can(int md){
	vector<int> b = a;
	for(int i=0;i<md;i++)
		swap(b[s[i].first],b[s[i].second]);
	int cnt = 0;
	for(int i=0;i<a.size();i++){
		while(b[i] != i){
			cnt ++;
			swap(b[i],b[b[i]]);
		}
	}
	return cnt <= md;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    for(int i=0;i<N;i++)a.push_back(S[i]);
    for(int i=0;i<M;i++)s.push_back({X[i],Y[i]});
    int md,lo=0,hi = M,ans;
	while(lo <= hi){
		md = (lo + hi)/2;
		if(can(md)){
			hi = md-1;
			ans = md;
		}else lo = md+1;
	}
	vector<int> b = a;
	for(int i=0;i<ans;i++)swap(a[s[i].first],a[s[i].second]);
	vector<pair<int,int>> c;
	for(int i=0;i<a.size();i++){
		while(a[i] != i){
			c.push_back({a[a[i]],a[i]});
			swap(a[i],a[a[i]]);
		}
	}
	a = b;
	while(c.size() < md)c.push_back({0,0});
	for(int i=0;i<N;i++)idx[a[i]] = i;
	for(int i=0;i<ans;i++){
		int l = s[i].first;
		int r = s[i].second;
		swap(idx[a[l]],idx[a[r]]);
		swap(a[l],a[r]);
		l = c[i].first;
		r = c[i].second;
		P[i] = idx[l];
		Q[i] = idx[r];
		swap(a[P[i]],a[Q[i]]);
		swap(idx[l],idx[r]);
	}
	return ans;
}

Compilation message (stderr)

sorting.cpp: In function 'bool can(int)':
sorting.cpp:18:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a.size();i++){
              ~^~~~~~~~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:41:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a.size();i++){
              ~^~~~~~~~~
sorting.cpp:48:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(c.size() < md)c.push_back({0,0});
        ~~~~~~~~~^~~~
sorting.cpp:30:24: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int md,lo=0,hi = M,ans;
                        ^~~
sorting.cpp:48:17: warning: 'md' may be used uninitialized in this function [-Wmaybe-uninitialized]
  while(c.size() < md)c.push_back({0,0});
        ~~~~~~~~~^~~~

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