답안 #257850

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
257850 2020-08-04T22:36:17 Z shrek12357 정렬하기 (IOI15_sorting) C++14
100 / 100
386 ms 24164 KB
#include<bits/stdc++.h> //:3
using namespace std;
typedef long long ll;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define rc(s) return cout<<s,0
#define pi pair <int, int>
#define sz(x) (int)((x).size())
#include "sorting.h"
 
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
 
const ll H = 1e6 + 11;
 
//ifstream in(".in");
//ofstream out(".out");
 
int pos[H], n, m;
pi query[H], ans[H], a[H];
 
bool check(int t, int S[]){
 
    int in[n + 11], out[n + 11];
 
    for(int i = 0; i < n; i++){
        in[i] = out[i] = S[i];
    }
 
    for(int i = 0; i < t; i++){
        swap(out[query[i].ff], out[query[i].ss]);
    }
 
    bool viz[n + 11];
    memset(viz, 0, sizeof(viz));
 
    int k = 0;
    for(int i = 0; i < n; i++){
 
        if(viz[i])continue;
 
        vector<int>cur;
 
        int v = out[i];
        while(v != i){
            cur.push_back(v);
            v = out[v];
        }
        cur.push_back(v);
 
        for(int j = sz(cur) - 1; j > 0; j--){
            a[k++] = {cur[0], cur[j]};
        }
 
        for(auto it : cur)viz[it] = 1;
    }
 
    if(k > t)return 0;
 
    for (int i = 0; i < n; ++i){
        pos[in[i]] = i;
    }
 
    for(int i = 0; i < k; i++){
 
        //His move
        int x = query[i].ff, y = query[i].ss;
        swap(in[x], in[y]);
        pos[in[x]] = x;
        pos[in[y]] = y;
 
        //My move
        x = pos[a[i].ff], y = pos[a[i].ss];
        swap(in[x], in[y]);
        pos[in[x]] = x;
        pos[in[y]] = y;
 
        ans[i] = {x, y};
    }
 
    while(k < t)ans[k++] = {0, 0};
 
    return 1;
} 
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 < m; i++){
      query[i].first = X[i];
      query[i].second = Y[i];
    }
  	int lo = -1;
	int hi = M;
	while (lo + 1 < hi) {
		int mid = (lo + hi) / 2;
		if (check(mid, S)) {
			hi = mid;
		}
		else {
			lo = mid;
		}
		//toChange.clear();
	}
	check(hi, S);
	//getAns(hi, S, N, X, Y);
	for (int i = 0; i < hi; i++) {
		P[i] = ans[i].first;
		Q[i] = ans[i].second;
	}
	return hi;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 2 ms 768 KB Output is correct
22 Correct 2 ms 768 KB Output is correct
23 Correct 2 ms 768 KB Output is correct
24 Correct 2 ms 768 KB Output is correct
25 Correct 2 ms 768 KB Output is correct
26 Correct 2 ms 768 KB Output is correct
27 Correct 2 ms 768 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 3 ms 640 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 3 ms 640 KB Output is correct
11 Correct 2 ms 640 KB Output is correct
12 Correct 2 ms 640 KB Output is correct
13 Correct 2 ms 640 KB Output is correct
14 Correct 2 ms 512 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 3 ms 640 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 3 ms 640 KB Output is correct
11 Correct 2 ms 640 KB Output is correct
12 Correct 2 ms 640 KB Output is correct
13 Correct 2 ms 640 KB Output is correct
14 Correct 2 ms 512 KB Output is correct
15 Correct 263 ms 21812 KB Output is correct
16 Correct 315 ms 21592 KB Output is correct
17 Correct 314 ms 23264 KB Output is correct
18 Correct 223 ms 18776 KB Output is correct
19 Correct 318 ms 21440 KB Output is correct
20 Correct 356 ms 21684 KB Output is correct
21 Correct 328 ms 21744 KB Output is correct
22 Correct 277 ms 23432 KB Output is correct
23 Correct 303 ms 24164 KB Output is correct
24 Correct 353 ms 23888 KB Output is correct
25 Correct 356 ms 23448 KB Output is correct
26 Correct 338 ms 20748 KB Output is correct
27 Correct 296 ms 19828 KB Output is correct
28 Correct 339 ms 22724 KB Output is correct
29 Correct 374 ms 21884 KB Output is correct
30 Correct 293 ms 18936 KB Output is correct
31 Correct 386 ms 22392 KB Output is correct
32 Correct 317 ms 23004 KB Output is correct
33 Correct 330 ms 23620 KB Output is correct
34 Correct 314 ms 22776 KB Output is correct
35 Correct 328 ms 20608 KB Output is correct
36 Correct 210 ms 17656 KB Output is correct
37 Correct 344 ms 23472 KB Output is correct
38 Correct 328 ms 22648 KB Output is correct
39 Correct 346 ms 22696 KB Output is correct