oj.uz

Submission #485853

# Submission time Handle Problem Language Result Execution time Memory
485853 2021-11-09T14:27:14 Z MilosMilutinovic Sorting (IOI15_sorting) C++14
74 / 100
 116 ms 13344 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
const ll mod2=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=201000;
int n,a[N],s[N],id[N],pos[N],x[N],y[N];

bool check(int r) {
	rep(i,0,n) a[i]=s[i],id[i]=i;
	rep(i,0,r) {
		swap(a[x[i]],a[y[i]]);
	}
	rep(i,0,n) pos[a[i]]=i;
	int cnt=0;
	rep(i,0,n) {
		if (pos[i]==i) continue;
		int w=a[i];
		swap(a[pos[i]],a[i]);
		swap(pos[i],pos[w]);
		cnt++;
	}
	return cnt<=r;
}

void gao(int r,int* p,int* q) {
	rep(i,0,n) a[i]=s[i],id[i]=i;
	rep(i,0,r) {
		swap(a[x[i]],a[y[i]]);
	}
	rep(i,0,n) pos[a[i]]=i;
	int cnt=0;
	vector<PII> todo;
	rep(i,0,n) {
		if (pos[i]==i) continue;
		todo.pb(mp(i,a[i]));
		int w=a[i];
		swap(a[pos[i]],a[i]);
		swap(pos[i],pos[w]);
	}
	assert(is_sorted(a,a+n));
	rep(i,0,n) a[i]=s[i],pos[a[i]]=i;
	rep(i,0,r) {
		swap(a[x[i]],a[y[i]]);
		swap(pos[a[x[i]]],pos[a[y[i]]]);
		if (i<SZ(todo)) {
			p[i]=pos[todo[i].fi];
			q[i]=pos[todo[i].se];
			swap(a[p[i]],a[q[i]]);	
			swap(pos[todo[i].fi],pos[todo[i].se]);
		} else p[i]=q[i]=0;
	}
	//rep(i,0,n) printf("%d ",a[i]); puts("");
	//assert(is_sorted(a,a+n));
	rep(i,SZ(todo),r) p[i]=q[i]=0;
}

int findSwapPairs(int n,int* s,int m,int* x,int* y,int* p,int* q) {
	if (is_sorted(s,s+n)) return 0;
	::n=n;
	rep(i,0,n) ::s[i]=s[i];
	rep(i,0,m) ::x[i]=x[i],::y[i]=y[i];
	int l=1,r=m,ans=1;
	while (l<=r) {
		int md=l+r>>1;
		if (check(md)) ans=md,r=md-1;
		else l=md+1;
	}
	gao(ans,p,q);
	return ans;
}

Compilation message

sorting.cpp: In function 'int rnd(int)':
sorting.cpp:18:33: warning: conversion from 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   18 | int rnd(int x) { return mrand() % x;}
      |                         ~~~~~~~~^~~
sorting.cpp: In function 'void gao(int, int*, int*)':
sorting.cpp:49:6: warning: unused variable 'cnt' [-Wunused-variable]
   49 |  int cnt=0;
      |      ^~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:75:50: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   75 | int findSwapPairs(int n,int* s,int m,int* x,int* y,int* p,int* q) {
      |                                             ~~~~~^
sorting.cpp:24:35: note: shadowed declaration is here
   24 | int n,a[N],s[N],id[N],pos[N],x[N],y[N];
      |                                   ^
sorting.cpp:75:43: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   75 | int findSwapPairs(int n,int* s,int m,int* x,int* y,int* p,int* q) {
      |                                      ~~~~~^
sorting.cpp:24:30: note: shadowed declaration is here
   24 | int n,a[N],s[N],id[N],pos[N],x[N],y[N];
      |                              ^
sorting.cpp:75:30: warning: declaration of 's' shadows a global declaration [-Wshadow]
   75 | int findSwapPairs(int n,int* s,int m,int* x,int* y,int* p,int* q) {
      |                         ~~~~~^
sorting.cpp:24:12: note: shadowed declaration is here
   24 | int n,a[N],s[N],id[N],pos[N],x[N],y[N];
      |            ^
sorting.cpp:75:23: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   75 | int findSwapPairs(int n,int* s,int m,int* x,int* y,int* p,int* q) {
      |                   ~~~~^
sorting.cpp:24:5: note: shadowed declaration is here
   24 | int n,a[N],s[N],id[N],pos[N],x[N],y[N];
      |     ^
sorting.cpp:82:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |   int md=l+r>>1;
      |          ~^~

Subtask #1
8.0 / 8.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 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 332 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 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 332 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 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 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 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 0 ms 332 KB Output is correct
18 Correct 0 ms 332 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 0 ms 216 KB Output is correct
21 Correct 1 ms 460 KB Output is correct
22 Correct 1 ms 460 KB Output is correct
23 Correct 1 ms 588 KB Output is correct
24 Correct 1 ms 460 KB Output is correct
25 Correct 2 ms 460 KB Output is correct
26 Correct 1 ms 588 KB Output is correct
27 Correct 1 ms 460 KB Output is correct

Subtask #5
20.0 / 20.0

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

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Incorrect 116 ms 13344 KB Output isn't correct
16 Halted 0 ms 0 KB -