oj.uz

Submission #314821

# Submission time Handle Problem Language Result Execution time Memory
314821 2020-10-21T11:21:16 Z amunduzbaev Sorting (IOI15_sorting) C++14
100 / 100
 378 ms 23348 KB 
//#include "grader.cpp"
#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
#define pb(a) push_back(a)
const int N=800005;
int n,s[N],x[N],y[N],tmp[N],pos[N];
vector<pair<int,int>> ans;
bool check(int m){
    int i;
    for(i=0;i<n;i++)tmp[i]=s[i];
    for(i=0;i<m;i++)swap(tmp[x[i]],tmp[y[i]]);
    for(i=0;i<n;i++)pos[tmp[i]]=i;
    vector<pair<int,int>    >sw;
    ans.clear();
    for(i=0;i<n;i++){
        if(pos[i]==i)continue;
        sw.push_back({tmp[i],tmp[pos[i]]});
        swap(tmp[pos[i]],tmp[i]);
        swap(pos[tmp[pos[i]]],pos[tmp[i]]);
    }
    if(sw.size()>m)return 0;
    for(i=0;i<n;i++)tmp[i]=s[i],pos[tmp[i]]=i;
    for(i=0;i<sw.size();i++){
        swap(tmp[x[i]],tmp[y[i]]);
        swap(pos[tmp[x[i]]],pos[tmp[y[i]]]);
        ans.push_back({pos[sw[i].first],pos[sw[i].second]});
        swap(tmp[pos[sw[i].first]],tmp[pos[sw[i].second]]);
        swap(pos[tmp[pos[sw[i].first]]],pos[tmp[pos[sw[i].second]]]);
    }
    for(;i<m;i++)ans.push_back({0,0});
    return 1;
}

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++) s[i]=S[i];
    for(int i=0;i<M;i++) x[i]=X[i], y[i]= Y[i];

    int l=0,r=M;
    while(l<r) {
        int mid=(l+r)/2;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    check(l);
    for(int i=0;i<l;i++){
        p[i]=ans[i].first, q[i]=ans[i].second;
    }
    return l;
}

Compilation message

sorting.cpp: In function 'bool check(int)':
sorting.cpp:22:17: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   22 |     if(sw.size()>m)return 0;
      |        ~~~~~~~~~^~
sorting.cpp:24:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(i=0;i<sw.size();i++){
      |             ~^~~~~~~~~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:35:76: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   35 | int findSwapPairs(int N, int S[], int M, int X[], int Y[], int p[], int q[]) {
      |                                                                            ^
sorting.cpp:6:11: note: shadowed declaration is here
    6 | const int N=800005;
      |           ^

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

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

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 3 ms 640 KB Output is correct
11 Correct 3 ms 640 KB Output is correct
12 Correct 2 ms 640 KB Output is correct
13 Correct 2 ms 640 KB Output is correct
14 Correct 1 ms 640 KB Output is correct
15 Correct 297 ms 21008 KB Output is correct
16 Correct 316 ms 21520 KB Output is correct
17 Correct 366 ms 22272 KB Output is correct
18 Correct 129 ms 20968 KB Output is correct
19 Correct 245 ms 22332 KB Output is correct
20 Correct 241 ms 22824 KB Output is correct
21 Correct 228 ms 22824 KB Output is correct
22 Correct 320 ms 22432 KB Output is correct
23 Correct 352 ms 22932 KB Output is correct
24 Correct 360 ms 22580 KB Output is correct
25 Correct 355 ms 22340 KB Output is correct
26 Correct 232 ms 22884 KB Output is correct
27 Correct 200 ms 22092 KB Output is correct
28 Correct 334 ms 22328 KB Output is correct
29 Correct 348 ms 21900 KB Output is correct
30 Correct 163 ms 20840 KB Output is correct
31 Correct 374 ms 22340 KB Output is correct
32 Correct 297 ms 22244 KB Output is correct
33 Correct 374 ms 22536 KB Output is correct
34 Correct 367 ms 22560 KB Output is correct
35 Correct 253 ms 22036 KB Output is correct
36 Correct 87 ms 20584 KB Output is correct
37 Correct 378 ms 23348 KB Output is correct
38 Correct 347 ms 22480 KB Output is correct
39 Correct 373 ms 22412 KB Output is correct