oj.uz

Submission #321757

# Submission time Handle Problem Language Result Execution time Memory
321757 2020-11-13T09:42:15 Z zaneyu Sorting (IOI15_sorting) C++14
100 / 100
 413 ms 31468 KB 
/*input
5
4 3 2 1 0
6
0 1
1 2
2 3
3 4
0 1
1 2

*/
//#include "supertrees.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#pragma GCC optimize("unroll-loops,no-stack-protector")
//order_of_key #of elements less than x
// find_by_order kth element
typedef long long int ll;
#define ld double
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
const ll maxn=6e5+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
const ll MOD=(1e9+7);
const ll MOD2=1000002173;
const ld PI=acos(-1);
const ld eps=1e-9;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
ll mult(ll a,ll b){
    return ((a%MOD)*(b%MOD))%MOD;
}
ll mypow(ll a,ll b,ll MOD){
    if(b<=0) return 1;
    ll res=1LL;
    while(b){
        if(b&1) res=(res*a)%MOD;
        a=(a*a)%MOD;
        b>>=1;
    }
    return res;
}
int d1[maxn],d2[maxn];
int posf[maxn],at[maxn];
int s[maxn],x[maxn],y[maxn];
int f[maxn],inv[maxn];
int p[maxn],q[maxn];
int n;
bool wk(int m){
	REP(i,n) d1[i]=d2[i]=s[i];
	REP(i,m){
		swap(d1[x[i]],d1[y[i]]);
	}
	REP(i,n) posf[d1[i]]=i,at[d2[i]]=i;
	REP(i,n) f[at[i]]=posf[i];
	REP(i,n) inv[f[i]]=i;
	int cur=0;
	REP(i,m){
		swap(f[x[i]],f[y[i]]);
		swap(at[d2[x[i]]],at[d2[y[i]]]);
		swap(d2[x[i]],d2[y[i]]);
		inv[f[x[i]]]=x[i],inv[f[y[i]]]=y[i];
		bool swp=0;
		while(cur<n){
			if(inv[cur]!=at[cur]){
				int a=inv[cur],b=at[cur];
				swap(at[d2[a]],at[d2[b]]);
				swap(d2[a],d2[b]);
				p[i]=a,q[i]=b;
				swp=1;
				++cur;
				break;
			}
			++cur;
		}
		if(!swp){
			p[i]=q[i]=0;
		}
	}
	REP(i,n){
		if(d2[i]!=i) return false;
	}
	return true;
}
int findSwapPairs(int _n, int S[], int m, int X[], int Y[], int P[], int Q[]) {
	n=_n;
	REP(i,n) s[i]=S[i];
	REP(i,m) x[i]=X[i],y[i]=Y[i];
	int l=0,r=m;
	while(l<r){
		//cout<<l<<' '<<r<<'\n';
		int mid=(l+r)/2;
		if(wk(mid)) r=mid;
		else l=mid+1;
	}
	wk(l);
	REP(i,l) P[i]=p[i],Q[i]=q[i];
	return l;
}

Compilation message

sorting.cpp: In function 'll mypow(ll, ll, ll)':
sorting.cpp:50:26: warning: declaration of 'MOD' shadows a global declaration [-Wshadow]
   50 | ll mypow(ll a,ll b,ll MOD){
      |                          ^
sorting.cpp:38:10: note: shadowed declaration is here
   38 | const ll MOD=(1e9+7);
      |          ^~~
sorting.cpp: In function 'bool wk(int)':
sorting.cpp:71:23: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   71 |  REP(i,n) posf[d1[i]]=i,at[d2[i]]=i;
      |                       ^
sorting.cpp:71:35: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   71 |  REP(i,n) posf[d1[i]]=i,at[d2[i]]=i;
      |                                   ^
sorting.cpp:73:21: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   73 |  REP(i,n) inv[f[i]]=i;
      |                     ^

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

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

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 620 KB Output is correct
2 Correct 2 ms 748 KB Output is correct
3 Correct 2 ms 620 KB Output is correct
4 Correct 2 ms 620 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 2 ms 748 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 3 ms 748 KB Output is correct
10 Correct 3 ms 748 KB Output is correct
11 Correct 3 ms 748 KB Output is correct
12 Correct 2 ms 748 KB Output is correct
13 Correct 3 ms 876 KB Output is correct
14 Correct 1 ms 620 KB Output is correct
15 Correct 266 ms 27884 KB Output is correct
16 Correct 310 ms 28268 KB Output is correct
17 Correct 397 ms 29804 KB Output is correct
18 Correct 140 ms 25068 KB Output is correct
19 Correct 287 ms 28524 KB Output is correct
20 Correct 288 ms 29292 KB Output is correct
21 Correct 294 ms 29420 KB Output is correct
22 Correct 256 ms 25324 KB Output is correct
23 Correct 295 ms 30988 KB Output is correct
24 Correct 398 ms 30700 KB Output is correct
25 Correct 413 ms 30188 KB Output is correct
26 Correct 294 ms 29420 KB Output is correct
27 Correct 277 ms 28652 KB Output is correct
28 Correct 390 ms 30440 KB Output is correct
29 Correct 398 ms 29804 KB Output is correct
30 Correct 221 ms 28012 KB Output is correct
31 Correct 384 ms 30572 KB Output is correct
32 Correct 302 ms 29932 KB Output is correct
33 Correct 401 ms 30572 KB Output is correct
34 Correct 343 ms 30572 KB Output is correct
35 Correct 288 ms 28140 KB Output is correct
36 Correct 115 ms 26860 KB Output is correct
37 Correct 400 ms 31468 KB Output is correct
38 Correct 411 ms 30188 KB Output is correct
39 Correct 388 ms 30316 KB Output is correct