제출 #129541

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
129541		Meloric	정렬하기 (IOI15_sorting)	C++14	0 / 100	1010 ms	524292 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>

#define pb push_back
#define pii pair<int, int>
#define X first
#define Y second
#define all(x) (x).begin(), (x).end()

using namespace std;
vector<vector<pii>> g;
vector<vector<pii>> ind;

vector<int> give(int time){
    vector<int> ans;
    for(int i = 0; i< g.size(); i++){
        int l = -1;
        int r = g[i].size()-1;
        while(r-l>1){
            int m = (r+l)/2;
            if(g[i][m].X >= time)r = m;
            else l = m;
        }
        ans.pb(g[i][r].Y);
    }
    return ans;
}
void dfs(int v, vector<int>& cur, vector<int>& vis){
    if(vis[v])return;
    vis[v] = 1;
    dfs(cur[v], cur, vis);
}
int cycles(vector<int>& cur){
    vector<int> vis;
    vis.assign(cur.size(), 0);
    int ans = 0;
    for(int i = 0; i< cur.size(); i++){
        if(!vis[i]){
            ans++;
            dfs(i, cur, vis);
        }
    }
    return ans;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    int flag = 0;
    for(int i = 0; i< N; i++){
        if(S[i]!=i)flag = 1;
    }
    if(!flag)return 0;
    g.assign(N, vector<pii>());
    ind.assign(N, vector<pii>());

    for(int i = 0; i< N; i++){
        g[i].pb({0, S[i]});
        ind[S[i]].pb({0, i});
    }
    for(int i = 0; i < M; i++){
        int nx, ny;
        nx = g[X[i]].back().Y;
        ny = g[Y[i]].back().Y;
        g[X[i]].pb({i+1, ny});
        g[Y[i]].pb({i+1, nx});
        ind[nx].pb({i+1, Y[i]});
        ind[ny].pb({i+1, X[i]});
    }
    int l = 0; int r = M;
    while(r-l>1){
        int m = (r+l)/2;
        vector<int> cur = give(m);
        if(N-cycles(cur)<=m)r = m;
        else l = m;
    }
    vector<int> cur = give(r);
    vector<pii> swp;
    for(int i = 0; i < cur.size(); i++){
        while(cur[i]!=i){
            swp.pb({cur[i], cur[cur[i]]});
            int a = cur[i]; int b = cur[cur[i]];
            cur[i] = b; cur[cur[i]] = a;
        }
    }
    int ans = r;
    for(int i = 0; i< r; i++){
        int ia, ib;
        ia = swp[i].X; ib = swp[i].Y;
        l = 0; r = ind[ia].size();
        while(r-l>1){
            int m = (r+l)/2;
            if(i+1<ind[ia][m].X)r = m;
            else l = m;
        }
        int fa, fb;
        fa = l;
        l = 0; r = ind[ib].size();
        while(r-l>1){
            int m = (r+l)/2;
            if(i+1<ind[ib][m].X)r = m;
            else l = m;
        }
        fb = l;
        P[i] = fb;
        Q[i] = fa;
    }
	return ans;
}

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

sorting.cpp: In function 'std::vector<int> give(int)':
sorting.cpp:16:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i< g.size(); i++){
                    ~^~~~~~~~~~
sorting.cpp:18:28: warning: conversion to 'int' from 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' may alter its value [-Wconversion]
         int r = g[i].size()-1;
                 ~~~~~~~~~~~^~
sorting.cpp: In function 'int cycles(std::vector<int>&)':
sorting.cpp:37:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i< cur.size(); i++){
                    ~^~~~~~~~~~~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:76:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < cur.size(); i++){
                    ~~^~~~~~~~~~~~
sorting.cpp:87:32: warning: conversion to 'int' from 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' may alter its value [-Wconversion]
         l = 0; r = ind[ia].size();
                    ~~~~~~~~~~~~^~
sorting.cpp:95:32: warning: conversion to 'int' from 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' may alter its value [-Wconversion]
         l = 0; r = ind[ib].size();
                    ~~~~~~~~~~~~^~

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