Submission #129536

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
129536	2019-07-12T13:03:40 Z	Meloric	Sorting (IOI15_sorting)	C++14	0 / 100	1000 ms	524292 KB

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(cur.size());
    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;
}

Compilation message

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:36: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:75:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < cur.size(); i++){
                    ~~^~~~~~~~~~~~
sorting.cpp:86: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:94: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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	3 ms	256 KB	Output is correct
3	Execution timed out	1090 ms	511556 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	3 ms	256 KB	Output is correct
3	Execution timed out	1090 ms	511556 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #3
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Runtime error	1002 ms	524288 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
3	Halted	0 ms	0 KB	-