제출 #726592

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

sorting

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "sorting.h"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout (T t, U...u) {cout << t << (sizeof... (u) ? ", " : ""), dout (u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back

const int SIZE = 2e5 + 5;

int n;
int a[SIZE], p[SIZE];
bool vs[SIZE];

bool ok(int r, int S[], int X[], int Y[]) {
    FOR (i, 0, n - 1) a[i] = S[i], vs[i] = 0;
    FOR (i, 0, r - 1) swap(a[X[i]], a[Y[i]]);
    int cnt = n;
    FOR (i, 0, n - 1) if (!vs[i]) {
        cnt--;
        for (int cur = i; !vs[cur]; cur = a[cur]) vs[cur] = 1;
    }
    return cnt <= r;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    n = N;
    int l = 0, r = M;
    while (l < r) {
        int mid = (l + r) / 2;
        if (ok(mid, S, X, Y)) r = mid;
        else l = mid + 1;
    }
    FOR (i, 0, n - 1) a[i] = S[i], vs[i] = 0;
    FOR (i, 0, r - 1) swap(a[X[i]], a[Y[i]]);
    int sz = 0;
    FOR (i, 0, n - 1) if (!vs[i]) {
        int last = -1, cur = i;
        while (!vs[cur]) {
            vs[cur] = 1;
            if (last != -1) P[sz] = last, Q[sz] = cur, sz++;
            last = cur;
            cur = a[cur];
        }
    }
    while (sz < r) P[sz] = Q[sz] = 0, sz++;
    FOR (i, 0, n - 1) p[S[i]] = i;
    FOR (i, 0, r - 1) {
        swap(p[S[X[i]]], p[S[Y[i]]]);
        swap(S[X[i]], S[Y[i]]);
        int a = P[i], b = Q[i];
        P[i] = p[a], Q[i] = p[b];
        swap(p[S[P[i]]], p[S[Q[i]]]);
        swap(S[P[i]], S[Q[i]]);
    }
    return r;
}

/*
in1
5
4 3 2 1 0
6
0 1
1 2
2 3
3 4
0 1
1 2
out1
3
0 4
1 3
3 4
in2
5
3 0 4 2 1
5
1 1
4 0
2 3
1 4
0 4
out2
3
1 4
4 2
2 2
*/

#ifdef WAIMAI
int main() {
	int N, M;
	cin >> N;
	int *S = (int*)malloc(sizeof(int) * (unsigned int)N);
	for (int i = 0; i < N; ++i) cin >> S[i];
	cin >> M;
	int *X = (int*)malloc(sizeof(int) * (unsigned int)M), *Y = (int*)malloc(sizeof(int) * (unsigned int)M);
	for (int i = 0; i < M; ++i) {
	    cin >> X[i];
	    cin >> Y[i];
	}
	int *P = (int*)malloc(sizeof(int) * (unsigned int)M), *Q = (int*)malloc(sizeof(int) * (unsigned int)M);
	int ans = findSwapPairs(N, S, M, X, Y, P, Q);
	cout << ans << '\n';
	for (int i = 0; i < ans; ++i) cout << P[i] << ' ' << Q[i] << '\n';
	return 0;
}
#endif

컴파일 시 표준 에러 (stderr) 메시지

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:66:13: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   66 |         int a = P[i], b = Q[i];
      |             ^
sorting.cpp:27:5: note: shadowed declaration is here
   27 | int a[SIZE], p[SIZE];
      |     ^

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