제출 #96896

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
96896		figter001	정렬하기 (IOI15_sorting)	C++14	100 / 100	259 ms	20456 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]]);
		}
	}
	while(c.size() < ans)c.push_back({0,0});
	a = b;
	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;
}

컴파일 시 표준 에러 (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:47:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(c.size() < ans)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;
                        ^~~

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