제출 #277637

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
277637		Mercenary	정렬하기 (IOI15_sorting)	C++14	20 / 100	2 ms	512 KiB

sorting

#include "sorting.h"
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef pair<int,int> ii;

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    int l = 0 , h = M;
    while(l <= h){
        int mid = l + h >> 1;
        vector<int> cur(N , 0) , pos(N , 0);
        for(int i = 0 ; i < N ; ++i)cur[i] = S[i] , pos[cur[i]] = i;
        for(int i = 0 ; i < mid ; ++i){
            swap(pos[cur[X[i]]] , pos[cur[Y[i]]]);
            swap(cur[X[i]] , cur[Y[i]]);
        }
        vector<ii> ans;
        for(int i = 0 ; i < N ; ++i){
            if(cur[i] != i){
                ans.pb(mp(i , cur[i]));
                int tmp = pos[i];
                swap(pos[i] , pos[cur[i]]);
                swap(cur[i] , cur[tmp]);
                assert(cur[i] == i);
                assert(pos[i] == i);
            }
        }
        for(int i = 0 ; i < N ; ++i)cur[i] = S[i] , pos[cur[i]] = i;
        if(ans.size() > mid)l = mid + 1;
        else h = mid - 1;
        for(int i = 0 ; i < mid ; ++i){
            P[i] = Q[i] = 0;
            swap(pos[cur[X[i]]] , pos[cur[Y[i]]]);
            swap(cur[X[i]] , cur[Y[i]]);
            if(i < ans.size()){
                P[i] = pos[ans[i].first];
                Q[i] = pos[ans[i].second];
                swap(cur[P[i]] , cur[Q[i]]);
                swap(pos[ans[i].first] , pos[ans[i].second]);
            }
        }
//        cout << mid << endl;
//        for(int i = 0 ; i < N ; ++i)cout << cur[i] << " ";
//        cout << endl;
    }
    return l;
}

#ifdef LOCAL
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "sorting.h"

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;
}
#endif // LOCAL

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

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:11:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   11 |         int mid = l + h >> 1;
      |                   ~~^~~
sorting.cpp:30:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |         if(ans.size() > mid)l = mid + 1;
      |            ~~~~~~~~~~~^~~~~
sorting.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |             if(i < ans.size()){
      |                ~~^~~~~~~~~~~~

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