oj.uz

Submission #723077

# Submission time Handle Problem Language Result Execution time Memory
723077 2023-04-13T08:20:45 Z sunwukong123 Sorting (IOI15_sorting) C++14
100 / 100
 180 ms 25660 KB 
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,s,e) for(int i = s; i <= (int)e; ++i)
#define DEC(i,s,e) for(int i = s; i >= (int)e; --i)
#define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
#define db(x) cerr << #x << "=" << x << "\n"
#define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n"
#define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n"
#define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n"
#define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{"  << ite.f << ',' << ite.s << "} "; cerr << "\n"
#define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n"
#define reach cerr << "LINE: " << __LINE__ << "\n";
#else
#define reach 
#define db(x)
#define db2(x,y)
#define db3(a,b,c)
#define dbv(v)
#define dbvp(v)
#define dba(a,ss,ee)
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define f first 
#define s second
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
#define g3(x) get<3>(x)
typedef pair <int, int> pi;
typedef tuple<int,int,int> ti3;
typedef tuple<int,int,int,int> ti4;
int rand(int a, int b) { return a + rng() % (b-a+1); }
const int MOD = 1e9 + 7;
const int inf = (int)1e9 + 500;
const long long oo = (long long)1e18 + 500;
template <typename T> void chmax(T& a, const T b) { a=max(a,b); }
template <typename T> void chmin(T& a, const T b) { a=min(a,b); }
const int MAXN = 600005;
int A[MAXN];
int n,m;
int X[MAXN], Y[MAXN];
int idx[MAXN];
struct ufds_{
	int p[MAXN],sz[MAXN];
	ufds_() {
		iota(p,p+MAXN,0);
		fill(sz,sz+MAXN,1);
	}
	int find(int x) {
		if(x==p[x])return x;
		else return p[x]=find(p[x]);
	}
	void merge(int x, int y) {
		x=find(x);y=find(y);
		if(x==y)return;
		if(sz[x]>=sz[y]){
			sz[x]+=sz[y];
			p[y]=x;
		} else {
			sz[y]+=sz[x];
			p[x]=y;
		}
	}
};
bool check(int ti) {
	//you can use ti operations to do everything
	
	FOR(i,0,ti-1) {
		swap(A[X[i]],A[Y[i]]);
	}
	FOR(i,0,n-1){
		idx[A[i]]=i;
	}
	db(ti);
	int res = 0;
	dba(A,0,n-1);
	FOR(i,0,n-1) {
		int y=idx[i];
		db2(i,y);
		if(i==y)continue;

		else {
			// swap index i to index y.
			db2(i,y);
			++res;
			swap(A[i],A[y]);
			swap(idx[A[i]],idx[A[y]]);
		}
	}
	dba(A,0,n-1);
	db2(res,ti);
	return res<=ti;

}
int findSwapPairs(int n, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	//FOR(i,0,n-1)A[i]=S[i];

	::n=n;
	::m=M;
	FOR(i,0,m-1)::X[i]=X[i];
	FOR(i,0,m-1)::Y[i]=Y[i];
	int lo=-1, hi=m+1;
	while(lo<hi-1) {
		FOR(i,0,n-1)A[i]=S[i];
		int mid=(lo+hi)/2;
		db(mid);
		if(check(mid))hi=mid;
		else lo=mid;

	}
	int R=hi;
	db(R);
	// i am doing R number of operations.
	FOR(i,0,n-1)A[i]=S[i];
	FOR(i,0,R-1) {
		swap(A[X[i]],A[Y[i]]);
	}
	vector<pi> ops;
	FOR(i,0,n-1){
		idx[A[i]]=i;
	}
	FOR(i,0,n-1) {
		int y=idx[i];
		if(i==y)continue;
		else {
			// swap index i to index y.
			ops.pb({A[i],A[y]});
			swap(A[i],A[y]);
			swap(idx[A[i]],idx[A[y]]);
		}
	}
	int c=0;
	vector<pi> tmp=ops;
	ops.clear();
	c=R-tmp.size();
	FOR(i,1,c)ops.pb({0,0});
	for(auto i:tmp)ops.pb(i);
	reverse(all(ops));

	FOR(i,0,n-1)A[i]=S[i];
	FOR(i,0,n-1)idx[A[i]]=i;
	
	FOR(i,0,R-1) {
		swap(A[X[i]],A[Y[i]]);
		swap(idx[A[X[i]]], idx[A[Y[i]]]);
		pi cur=ops.back(); ops.pop_back();
		int val1=cur.f, val2=cur.s;
		int Aidx=idx[val1], Bidx=idx[val2];
		


		P[i]=Aidx; Q[i]=Bidx;

		swap(A[Aidx],A[Bidx]);
		swap(idx[val1],idx[val2]);

		
	}
	FOR(i,0,n-1)assert(A[i]==i);
	return R;


}

Compilation message

sorting.cpp: In function 'int rand(int, int)':
sorting.cpp:36:35: 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]
   36 | int rand(int a, int b) { return a + rng() % (b-a+1); }
      |                                 ~~^~~~~~~~~~~~~~~~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:99:55: warning: declaration of 'Y' shadows a global declaration [-Wshadow]
   99 | int findSwapPairs(int n, int S[], int M, int X[], int Y[], int P[], int Q[]) {
      |                                                   ~~~~^~~
sorting.cpp:45:14: note: shadowed declaration is here
   45 | int X[MAXN], Y[MAXN];
      |              ^
sorting.cpp:99:46: warning: declaration of 'X' shadows a global declaration [-Wshadow]
   99 | int findSwapPairs(int n, int S[], int M, int X[], int Y[], int P[], int Q[]) {
      |                                          ~~~~^~~
sorting.cpp:45:5: note: shadowed declaration is here
   45 | int X[MAXN], Y[MAXN];
      |     ^
sorting.cpp:99:23: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   99 | int findSwapPairs(int n, int S[], int M, int X[], int Y[], int P[], int Q[]) {
      |                   ~~~~^
sorting.cpp:44:5: note: shadowed declaration is here
   44 | int n,m;
      |     ^
sorting.cpp:139:5: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  139 |  c=R-tmp.size();
      |    ~^~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

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

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 2 ms 468 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 146 ms 14924 KB Output is correct
16 Correct 143 ms 23140 KB Output is correct
17 Correct 169 ms 24296 KB Output is correct
18 Correct 70 ms 19088 KB Output is correct
19 Correct 125 ms 22628 KB Output is correct
20 Correct 138 ms 23372 KB Output is correct
21 Correct 142 ms 23488 KB Output is correct
22 Correct 144 ms 19744 KB Output is correct
23 Correct 158 ms 25428 KB Output is correct
24 Correct 169 ms 25020 KB Output is correct
25 Correct 157 ms 24580 KB Output is correct
26 Correct 147 ms 23380 KB Output is correct
27 Correct 118 ms 22504 KB Output is correct
28 Correct 175 ms 24644 KB Output is correct
29 Correct 178 ms 24112 KB Output is correct
30 Correct 99 ms 21828 KB Output is correct
31 Correct 171 ms 24816 KB Output is correct
32 Correct 152 ms 24544 KB Output is correct
33 Correct 178 ms 24892 KB Output is correct
34 Correct 175 ms 24744 KB Output is correct
35 Correct 127 ms 22288 KB Output is correct
36 Correct 64 ms 20532 KB Output is correct
37 Correct 180 ms 25660 KB Output is correct
38 Correct 173 ms 24640 KB Output is correct
39 Correct 168 ms 24744 KB Output is correct