oj.uz

Submission #389619

# Submission time Handle Problem Language Result Execution time Memory
389619 2021-04-14T09:49:25 Z faresbasbs Sorting (IOI15_sorting) C++14
100 / 100
 328 ms 34008 KB 
#include <bits/stdc++.h>
#include "sorting.h"
using namespace std;
vector<int> v,v2,st,e,l,r,ls,rs;
int n,rt;

bool work(int mid){
    l.clear(),r.clear(),ls.clear(),rs.clear();
    v2 = v;
    for(int i = 0 ; i < mid ; i += 1){
        swap(v2[st[i]],v2[e[i]]);
    }
    int num = 0;
    for(int i = 0 ; i < n ; i += 1){
        while(v2[i] != i){
            l.push_back(v2[i]) , r.push_back(v2[v2[i]]);
            swap(v2[i],v2[v2[i]]);
            num += 1;
        }
    }
    while(num < mid){
        l.push_back(0) , r.push_back(0);
        num += 1;
    }
    if(num > mid){
        return false;
    }
    vector<int> ind(n);
    v2 = v;
    for(int i = 0 ; i < n ; i += 1){
        ind[v2[i]] = i;
    }
    for(int i = 0 ; i < mid ; i += 1){
        int x = st[i] , y = e[i];
        swap(ind[v2[x]],ind[v2[y]]);
        swap(v2[x],v2[y]);
        x = l[i] , y = r[i];
        ls.push_back(ind[x]);
        rs.push_back(ind[y]);
        swap(v2[ind[x]],v2[ind[y]]);
        swap(ind[x],ind[y]);
    }
    return true;
}

int findSwapPairs(int N , int s[] , int m , int x[] , int y[] , int p[] , int q[]){
    n = N;
    for(int i = 0 ; i < n ; i += 1){
        v.push_back(s[i]);
    }
    for(int i = 0 ; i < m ; i += 1){
        st.push_back(x[i]) , e.push_back(y[i]);
    }
    int first = -1 , last = m;
    while(last-first > 1){
        int mid = (first+last)/2;
        if(work(mid)){
            last = mid;
        }else{
            first = mid;
        }
    }
    work(last);
    for(int i = 0 ; i < (int)ls.size() ; i += 1){
        p[i] = ls[i] , q[i] = rs[i];
    }
    return last;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 332 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 2 ms 716 KB Output is correct
22 Correct 2 ms 716 KB Output is correct
23 Correct 2 ms 820 KB Output is correct
24 Correct 2 ms 716 KB Output is correct
25 Correct 2 ms 716 KB Output is correct
26 Correct 2 ms 716 KB Output is correct
27 Correct 2 ms 716 KB Output is correct

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 2 ms 588 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 2 ms 588 KB Output is correct
13 Correct 2 ms 588 KB Output is correct
14 Correct 1 ms 588 KB Output is correct
15 Correct 230 ms 30540 KB Output is correct
16 Correct 275 ms 31168 KB Output is correct
17 Correct 308 ms 32940 KB Output is correct
18 Correct 122 ms 28708 KB Output is correct
19 Correct 199 ms 31888 KB Output is correct
20 Correct 218 ms 32048 KB Output is correct
21 Correct 202 ms 32076 KB Output is correct
22 Correct 235 ms 27876 KB Output is correct
23 Correct 265 ms 32972 KB Output is correct
24 Correct 320 ms 33308 KB Output is correct
25 Correct 328 ms 33460 KB Output is correct
26 Correct 214 ms 31912 KB Output is correct
27 Correct 193 ms 31712 KB Output is correct
28 Correct 287 ms 33020 KB Output is correct
29 Correct 300 ms 32996 KB Output is correct
30 Correct 161 ms 30796 KB Output is correct
31 Correct 311 ms 33104 KB Output is correct
32 Correct 288 ms 32524 KB Output is correct
33 Correct 301 ms 33508 KB Output is correct
34 Correct 270 ms 33228 KB Output is correct
35 Correct 200 ms 31564 KB Output is correct
36 Correct 98 ms 29652 KB Output is correct
37 Correct 307 ms 34008 KB Output is correct
38 Correct 290 ms 33236 KB Output is correct
39 Correct 303 ms 33744 KB Output is correct