oj.uz

Submission #133628

# Submission time Handle Problem Language Result Execution time Memory
133628 2019-07-21T07:02:56 Z ckodser Sorting (IOI15_sorting) C++14
74 / 100
 606 ms 524292 KB 
#include "sorting.h"
#include<bits/stdc++.h>

#define ll int
#define pb push_back
#define ld long double
#define mp make_pair
#define F first
#define S second
#define pii pair<ll,ll> 

using namespace :: std;

const ll maxn=2e5+500;
const ll inf=1e9+900;

ll per[maxn];
ll s[maxn];
ll x[maxn];
ll y[maxn];
ll n,m;
vector<pii> vec;

void dfs(ll a){
    if(per[a]==a)return;
    vec.pb(mp(a,per[a]));
    swap(per[a],per[per[a]]);
    dfs(a);
}
void copytoper(){
    for(ll i=0;i<n;i++){
	per[i]=s[i];
    }
}
bool mishe(ll mid){
    copytoper();
    for(ll i=0;i<mid;i++){
	swap(per[x[i]],per[y[i]]);
    }
    vec.clear();
    for(ll i=0;i<n;i++){
	dfs(i);
    }
    return (vec.size()<=mid);
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    n=N,m=M;
    for(ll i=0;i<n;i++){
	s[i]=S[i];
    }
    for(ll i=0;i<m;i++){
	x[i]=X[i];
	y[i]=Y[i];
    }
    ll b=-1;
    ll e=M;
    while(e-b>1){
	ll mid=(e+b)/2;
	if(mishe(mid)){
	    e=mid;
	}else{
	    b=mid;
	}
    }
    // ans=e;
    copytoper();
    for(ll i=0;i<e;i++){
	swap(per[x[i]],per[y[i]]);
    }
    vec.clear();
    for(ll i=0;i<n;i++){
	dfs(i);
    }
    while(vec.size()<e){
	vec.pb(mp(0,0));
    }
    if(vec.size()>e){
	return 0;
    }
    for(ll i=0;i<n;i++){
	per[i]=i;
    }
    for(ll i=e-1;i>=0;i--){
	swap(per[x[i]],per[y[i]]);
    }
    vector<pii> ans;
    for(ll i=0;i<e;i++){
	swap(per[x[i]],per[y[i]]);
	pii a=vec[i];
	ll b1,b2;
	for(ll i=0;i<n;i++){
	    if(per[i]==a.F)b1=i;
	    if(per[i]==a.S)b2=i;
	}
	ans.pb(mp(b1,b2));
    }
    for(ll i=0;i<e;i++){
	P[i]=ans[i].F;
	Q[i]=ans[i].S;
    }
    copytoper();
    for(ll i=0;i<e;i++){
	swap(per[x[i]],per[y[i]]);
	swap(per[Q[i]],per[P[i]]);
    }
    for(ll i=0;i<n;i++){
	if(per[i]!=i){
	    return 0;
	}
    }
    return e;
}

Compilation message

sorting.cpp: In function 'bool mishe(int)':
sorting.cpp:44:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     return (vec.size()<=mid);
             ~~~~~~~~~~^~~~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:74:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(vec.size()<e){
           ~~~~~~~~~~^~
sorting.cpp:77:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(vec.size()>e){
        ~~~~~~~~~~^~
sorting.cpp:91:9: warning: declaration of 'i' shadows a previous local [-Wshadow]
  for(ll i=0;i<n;i++){
         ^
sorting.cpp:87:12: note: shadowed declaration is here
     for(ll i=0;i<e;i++){
            ^
sorting.cpp:95:11: warning: 'b2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  ans.pb(mp(b1,b2));
           ^
sorting.cpp:95:11: warning: 'b1' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 424 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 3 ms 632 KB Output is correct
22 Correct 3 ms 760 KB Output is correct
23 Correct 3 ms 760 KB Output is correct
24 Correct 3 ms 632 KB Output is correct
25 Correct 3 ms 760 KB Output is correct
26 Correct 4 ms 760 KB Output is correct
27 Correct 4 ms 632 KB Output is correct

Subtask #5
20.0 / 20.0

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

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 632 KB Output is correct
2 Correct 14 ms 760 KB Output is correct
3 Correct 7 ms 632 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 4 ms 632 KB Output is correct
7 Correct 6 ms 632 KB Output is correct
8 Correct 7 ms 632 KB Output is correct
9 Correct 7 ms 632 KB Output is correct
10 Correct 7 ms 632 KB Output is correct
11 Correct 6 ms 632 KB Output is correct
12 Correct 5 ms 632 KB Output is correct
13 Correct 7 ms 680 KB Output is correct
14 Correct 2 ms 504 KB Output is correct
15 Runtime error 606 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -