제출 #1059200

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

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 200005
#define ll long long
#define FOR(i, a, b) for(ll i = a; i <= b; i++)


int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    ll l = 0, h = M;
    while(l < h){
        int m = (l + h) / 2;
        int s[N], slc[N];
        FOR(i, 0, N - 1) s[i] = i;
        for(int i = m - 1; i >= 0; i--){
            swap(s[X[i]], s[Y[i]]);
        }
        FOR(i, 0, N - 1) slc[s[i]] = i; 

        queue<int> q;

        int s2[N], lc[N];
        FOR(i, 0, N - 1) s2[i] = S[i], lc[S[i]] = i;
        FOR(i, 0, N - 1) if(slc[i] != lc[i]) q.push(i);

        FOR(i, 0, m - 1){
            swap(s[X[i]], s[Y[i]]), swap(slc[s[X[i]]], slc[s[Y[i]]]);
            swap(s2[X[i]], s2[Y[i]]), swap(lc[s2[X[i]]], lc[s2[Y[i]]]);

            while(q.size() && slc[q.front()] == lc[q.front()]){
                q.pop();
            }
            if(q.size()){
                int qi = q.front(); q.pop();
                P[i] = slc[qi];
                Q[i] = lc[qi];
                swap(s2[P[i]], s2[Q[i]]), swap(lc[s2[P[i]]], lc[s2[Q[i]]]);
            }else{
                P[i] = Q[i] = 0;
            }
        }
        
        FOR(i, 0, N - 1) if(s[i] != s2[i]) {
            l = m + 1;
            goto spot1;
        }
        h = m;
        spot1:;
    }

// fdasfd 
    int m = l;
    int s[N], slc[N];
    FOR(i, 0, N - 1) s[i] = i;
    for(int i = m - 1; i >= 0; i--){
        swap(s[X[i]], s[Y[i]]);
    }
    FOR(i, 0, N - 1) slc[s[i]] = i; 

    queue<int> q;

    int s2[N], lc[N];
    FOR(i, 0, N - 1) s2[i] = S[i], lc[S[i]] = i;
    FOR(i, 0, N - 1) if(slc[i] != lc[i]) q.push(i);

    FOR(i, 0, m - 1){
        swap(s[X[i]], s[Y[i]]), swap(slc[s[X[i]]], slc[s[Y[i]]]);
        swap(s2[X[i]], s2[Y[i]]), swap(lc[s2[X[i]]], lc[s2[Y[i]]]);

        while(q.size() && slc[q.front()] == lc[q.front()]){
            q.pop();
        }
        if(q.size()){
            int qi = q.front(); q.pop();
            P[i] = slc[qi];
            Q[i] = lc[qi];
            swap(s2[P[i]], s2[Q[i]]), swap(lc[s2[P[i]]], lc[s2[Q[i]]]);
        }else{
            P[i] = Q[i] = 0;
        }
    }

	return l;
}

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

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:12:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   12 |         int m = (l + h) / 2;
      |                 ~~~~~~~~^~~
sorting.cpp:14:33: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   14 |         FOR(i, 0, N - 1) s[i] = i;
      |                                 ^
sorting.cpp:18:38: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   18 |         FOR(i, 0, N - 1) slc[s[i]] = i;
      |                                      ^
sorting.cpp:23:51: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   23 |         FOR(i, 0, N - 1) s2[i] = S[i], lc[S[i]] = i;
      |                                                   ^
sorting.cpp:24:53: warning: conversion from 'long long int' to 'std::queue<int>::value_type' {aka 'int'} may change value [-Wconversion]
   24 |         FOR(i, 0, N - 1) if(slc[i] != lc[i]) q.push(i);
      |                                                     ^
sorting.cpp:52:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   52 |     int m = l;
      |             ^
sorting.cpp:54:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   54 |     FOR(i, 0, N - 1) s[i] = i;
      |                             ^
sorting.cpp:58:34: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   58 |     FOR(i, 0, N - 1) slc[s[i]] = i;
      |                                  ^
sorting.cpp:63:47: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   63 |     FOR(i, 0, N - 1) s2[i] = S[i], lc[S[i]] = i;
      |                                               ^
sorting.cpp:64:49: warning: conversion from 'long long int' to 'std::queue<int>::value_type' {aka 'int'} may change value [-Wconversion]
   64 |     FOR(i, 0, N - 1) if(slc[i] != lc[i]) q.push(i);
      |                                                 ^
sorting.cpp:83:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   83 |  return l;
      |         ^

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