제출 #869957

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
869957		qin	정렬하기 (IOI15_sorting)	C++17	100 / 100	224 ms	29944 KiB

sorting

#ifdef LOCAL
#else
#include "sorting.h"
#endif
#include <bits/stdc++.h>
#define fi first
#define se second
#define ssize(x) int(x.size())
#define pn printf("\n")
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef double db;
int inf = 2e09; ll infll = 2e18; int mod = 1e09+7;
int findSwapPairs(int n, int s[], int m, int x[], int y[], int P[], int Q[]){
		vector<int> t(n); //skalowanie
		for(int i = 0; i < n; ++i) t[i] = s[i];
		sort(t.begin(), t.end());
		unordered_map<int, int> mp;
		for(int i = 0; i < n; ++i) mp[t[i]] = i;
		for(int i = 0; i < n; ++i) s[i] = mp[s[i]];
		bool isSorted = 1; // sprawdzenie, czy ciąg jest już posortowany
		for(int i = 1; i < n; ++i) if(s[i-1] > s[i]) isSorted = 0;
		if(isSorted) return 0;
		
		int l = 1, r = m, mid;
		vector<int> where_to_put(n), pos(n), where_in_wtp(n);
		while(1){
				bool endnow = l == r;
				mid = (l+r)>>1;
				for(int i = 0; i < n; ++i) t[i] = s[i], pos[s[i]] = i, where_to_put[i] = i;
				for(int i = 0; i < mid; ++i) swap(t[x[i]], t[y[i]]), swap(pos[t[x[i]]], pos[t[y[i]]]), swap(where_to_put[x[i]], where_to_put[y[i]]);
				for(int i = 0; i < n; ++i) t[i] = s[i], pos[t[i]] = i, where_in_wtp[where_to_put[i]] = i;
				/*for(int j = 0; j < n; ++j) printf("%d ", where_to_put[j]);
				pn;
				for(int j = 0; j < n; ++j) printf("%d ", where_in_wtp[j]);
				pn;
				pn;*/
				int cur = 0, tmp;
				for(int i = 0; i < mid; ++i){
						//for(int j = 0; j < n; ++j) printf("%d ", t[j]);
						//pn;
						//printf("%d %d - %d %d\n", where_to_put[where_in_wtp[x[i]]], where_to_put[where_in_wtp[y[i]]], where_in_wtp[x[i]], where_in_wtp[y[i]]);
						swap(pos[t[x[i]]], pos[t[y[i]]]);
						swap(where_to_put[where_in_wtp[x[i]]], where_to_put[where_in_wtp[y[i]]]);
						
						swap(where_in_wtp[x[i]], where_in_wtp[y[i]]);
						swap(t[x[i]], t[y[i]]);
						//for(int j = 0; j < n; ++j) printf("%d ", t[j]);
						//pn;
						while(cur < n){
								if(pos[cur] == where_to_put[cur]) ++cur;
								else{
										P[i] = pos[cur], Q[i] = where_to_put[cur];
										tmp = pos[cur];
										swap(pos[cur], pos[t[where_to_put[cur]]]);
										swap(t[tmp], t[where_to_put[cur]]);
										break;
								}
						}
						if(n <= cur) P[i] = 0, Q[i] = 0;
						//printf("%d\n", cur);
				}
				if(endnow) break;
				isSorted = 1;
				for(int i = 1; i < n; ++i) if(t[i-1] > t[i]) isSorted = 0;
				if(isSorted) r = mid;
				else l = mid+1;
		}
		//printf("%d %d\n", n, m);
		for(int i = 0; i < l; ++i) if(P[i] > Q[i]) swap(P[i], Q[i]);
		return l;
}
#ifdef LOCAL
int main(){
		//int T = 1;
		//for(++T; --T; ) answer();
		return 0;
}
#endif

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