제출 #567907

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
567907		hoanghq2004	정렬하기 (IOI15_sorting)	C++14	100 / 100	189 ms	16100 KiB

sorting

#include <bits/stdc++.h>
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "sorting.h"

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;


int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    int L = 0, R = M;
    auto check = [&](int mid) {
        vector <int> p(N);
        for (int i = 0; i < N; ++i) p[i] = S[i];
        for (int i = 0; i < mid; ++i) swap(p[X[i]], p[Y[i]]);
        int comp = 0;
        vector <int> vis(N, 0);
        for (int u = 0; u < N; ++u) {
            if (vis[u]) continue;
            ++comp;
            int v = u;
            do {
                vis[v] = 1;
                v = p[v];
            } while (u != v);
        }
        return (N - comp <= mid);
    };
    while (L < R) {
        int mid = L + R >> 1;
        if (check(mid)) R = mid;
        else L = mid + 1;
    }

    vector <int> pos(N);
    for (int i = 0; i < L; ++i) swap(S[X[i]], S[Y[i]]);
    vector <int> vis(N, 0);
    vector <pair <int, int>> need;
    for (int u = 0; u < N; ++u) {
        if (vis[u]) continue;
        int v = u;
        do {
            if (S[v] != u) need.push_back({v, S[v]});
            vis[v] = 1;
            v = S[v];
        } while (u != v);
    }
    for (int i = L - 1; i >= 0; --i) swap(S[X[i]], S[Y[i]]);
    while (need.size() < L) need.push_back({0, 0});
    for (int i = 0; i < N; ++i) pos[S[i]] = i;
    for (int i = 0; i < L; ++i) {
        swap(pos[S[X[i]]], pos[S[Y[i]]]);
        swap(S[X[i]], S[Y[i]]);
        auto &[u, v] = need[i];
        u = pos[u], v = pos[v];
        P[i] = u, Q[i] = v;
        swap(pos[S[u]], pos[S[v]]);
        swap(S[u], S[v]);
    }
    return L;
}


//static char _buffer[1024];
//static int _currentChar = 0;
//static int _charsNumber = 0;
//static FILE *_inputFile, *_outputFile;
//
//static inline int _read() {
//    if (_charsNumber < 0) {
//        exit(1);
//    }
//    if (!_charsNumber || _currentChar == _charsNumber) {
//        _charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), _inputFile);
//        _currentChar = 0;
//    }
//    if (_charsNumber <= 0) {
//        return -1;
//    }
//    return _buffer[_currentChar++];
//}
//
//static inline int _readInt() {
//    int c, x, s;
//    c = _read();
//    while (c <= 32) c = _read();
//    x = 0;
//    s = 1;
//    if (c == '-') {
//        s = -1;
//        c = _read();
//    }
//    while (c > 32) {
//        x *= 10;
//        x += c - '0';
//        c = _read();
//    }
//    if (s < 0) x = -x;
//    return x;
//}
//
//
//int main()
//{
//	_inputFile = fopen("sorting.in", "rb");
//	_outputFile = fopen("sorting.out", "w");
//	int N, M;
//	N = _readInt();
//	int *S = (int*)malloc(sizeof(int) * (unsigned int)N);
//	for (int i = 0; i < N; ++i)
//		S[i] = _readInt();
//	M = _readInt();
//	int *X = (int*)malloc(sizeof(int) * (unsigned int)M), *Y = (int*)malloc(sizeof(int) * (unsigned int)M);
//	for (int i = 0; i < M; ++i) {
//	    X[i] = _readInt();
//	    Y[i] = _readInt();
//	}
//	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);
//	fprintf(_outputFile, "%d\n", ans);
//	for (int i = 0; i < ans; ++i)
//		fprintf(_outputFile, "%d %d\n", P[i], Q[i]);
//	return 0;
//}
//

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

sorting.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
sorting.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:35:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |         int mid = L + R >> 1;
      |                   ~~^~~
sorting.cpp:54:24: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |     while (need.size() < L) need.push_back({0, 0});
      |            ~~~~~~~~~~~~^~~
sorting.cpp:59:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |         auto &[u, v] = need[i];
      |               ^

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