oj.uz

Submission #103523

# Submission time Handle Problem Language Result Execution time Memory
103523 2019-03-31T01:15:17 Z Osama_Alkhodairy Sorting (IOI15_sorting) C++17
100 / 100
 733 ms 31312 KB 
#include <bits/stdc++.h>
#include "sorting.h"
//#include "grader.cpp"
using namespace std;

int n, m;
vector <int> s;
vector <pair <int, int> > w;

vector <pair <int, int> > swaps(vector <int> &a){
    vector <bool> vis(n);
    vector <pair <int, int> > swaps;
    for(int i = 0 ; i < n ; i++){
        if(vis[i]) continue;
        vector <int> cycle;
        int cur = i;
        while(vis[cur] == 0){
            cycle.push_back(cur);
            vis[cur] = 1;
            cur = a[cur];
        }
        for(int i = 1 ; i < (int)cycle.size() ; i++){
            swaps.emplace_back(cycle[0], cycle[i]);
        }
    }
    vector <int> b = a;
    vector <pair <int, int> > ret;
    for(auto &i : swaps){
        ret.emplace_back(b[i.first], b[i.second]);
        swap(b[i.first], b[i.second]);
    }
    return ret;
}
vector <pair <int, int> > check(int mid){
    vector <int> a = s;
    for(int i = 0 ; i < mid ; i++){
        swap(a[w[i].first], a[w[i].second]);
    }
    auto c = swaps(a);
    if((int)c.size() > mid){
        return vector <pair <int, int> >(1, make_pair(-1, -1));
    }
    a = s;
    vector <int> pos(n);
    for(int i = 0 ; i < n ; i++){
        pos[a[i]] = i;
    }
    auto adjust = [&](int idx){
        pos[a[idx]] = idx;
    };
    vector <pair <int, int> > ret;
    for(int i = 0 ; i < mid ; i++){
        swap(a[w[i].first], a[w[i].second]);
        adjust(w[i].first);
        adjust(w[i].second);
        if(i >= (int)c.size()) ret.emplace_back(0, 0);
        else{
            ret.emplace_back(pos[c[i].first], pos[c[i].second]);
            swap(a[pos[c[i].first]], a[pos[c[i].second]]);
            adjust(pos[c[i].first]);
            adjust(pos[c[i].second]);
        }
    }
    return ret;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    n = N;
    m = M;
    for(int i = 0 ; i < n ; i++)
        s.push_back(S[i]);
    for(int i = 0 ; i < m ; i++)
        w.emplace_back(X[i], Y[i]);
    int l = 0, r = m;
    while(l <= r){
        int mid = (l + r) / 2;
        auto c = check(mid);
        if(c.size() == 0 || c[0].first != -1) r = mid - 1;
        else l = mid + 1;
    }
    r++;
    if(r == 0) return 0;
    auto ans = check(r);
    int sz = ans.size();
    for(int i = 0 ; i < sz ; i++){
        P[i] = ans[i].first;
        Q[i] = ans[i].second;
    }
	return sz;
}

Compilation message

sorting.cpp: In function 'std::vector<std::pair<int, int> > swaps(std::vector<int>&)':
sorting.cpp:22:17: warning: declaration of 'i' shadows a previous local [-Wshadow]
         for(int i = 1 ; i < (int)cycle.size() ; i++){
                 ^
sorting.cpp:13:13: note: shadowed declaration is here
     for(int i = 0 ; i < n ; i++){
             ^
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:83:22: warning: conversion to 'int' from 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' may alter its value [-Wconversion]
     int sz = ans.size();
              ~~~~~~~~^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 400 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 400 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 640 KB Output is correct
6 Correct 3 ms 256 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 400 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 3 ms 640 KB Output is correct
18 Correct 3 ms 256 KB Output is correct
19 Correct 2 ms 256 KB Output is correct
20 Correct 2 ms 432 KB Output is correct
21 Correct 4 ms 776 KB Output is correct
22 Correct 3 ms 768 KB Output is correct
23 Correct 5 ms 896 KB Output is correct
24 Correct 4 ms 896 KB Output is correct
25 Correct 5 ms 896 KB Output is correct
26 Correct 4 ms 768 KB Output is correct
27 Correct 3 ms 896 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 4 ms 640 KB Output is correct
5 Correct 6 ms 768 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 4 ms 640 KB Output is correct
8 Correct 4 ms 640 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 5 ms 640 KB Output is correct
11 Correct 4 ms 640 KB Output is correct
12 Correct 5 ms 640 KB Output is correct
13 Correct 5 ms 640 KB Output is correct
14 Correct 6 ms 640 KB Output is correct

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 4 ms 640 KB Output is correct
5 Correct 6 ms 768 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 4 ms 640 KB Output is correct
8 Correct 4 ms 640 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 5 ms 640 KB Output is correct
11 Correct 4 ms 640 KB Output is correct
12 Correct 5 ms 640 KB Output is correct
13 Correct 5 ms 640 KB Output is correct
14 Correct 6 ms 640 KB Output is correct
15 Correct 371 ms 26688 KB Output is correct
16 Correct 542 ms 28028 KB Output is correct
17 Correct 507 ms 29392 KB Output is correct
18 Correct 274 ms 28504 KB Output is correct
19 Correct 594 ms 29908 KB Output is correct
20 Correct 543 ms 30292 KB Output is correct
21 Correct 431 ms 30420 KB Output is correct
22 Correct 495 ms 23900 KB Output is correct
23 Correct 543 ms 30172 KB Output is correct
24 Correct 530 ms 29184 KB Output is correct
25 Correct 623 ms 29752 KB Output is correct
26 Correct 530 ms 28752 KB Output is correct
27 Correct 466 ms 28240 KB Output is correct
28 Correct 575 ms 29512 KB Output is correct
29 Correct 687 ms 30152 KB Output is correct
30 Correct 429 ms 28244 KB Output is correct
31 Correct 733 ms 30656 KB Output is correct
32 Correct 474 ms 29280 KB Output is correct
33 Correct 502 ms 29784 KB Output is correct
34 Correct 449 ms 30568 KB Output is correct
35 Correct 549 ms 29396 KB Output is correct
36 Correct 240 ms 27868 KB Output is correct
37 Correct 541 ms 31312 KB Output is correct
38 Correct 518 ms 30132 KB Output is correct
39 Correct 493 ms 30324 KB Output is correct