oj.uz

Submission #599607

# Submission time Handle Problem Language Result Execution time Memory
599607 2022-07-19T16:28:06 Z beaconmc Sorting (IOI15_sorting) C++14
100 / 100
 486 ms 46556 KB 
//#include "sorting.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")

typedef long long ll;
using namespace std;

#define ll int
#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)

ll n,s[600001],m,x[600001],y[600001],p[600001],q[600001], realsus[600001];
vector<vector<ll>> temp;

int check(ll k){
	vector<ll> sus;

	temp.clear();
	FOR(i,0,n){
		sus.push_back(s[i]);
		realsus[s[i]] = i;
	}

	FOR(i,0,k){
		swap(realsus[sus[x[i]]], realsus[sus[y[i]]]);
		swap(sus[x[i]], sus[y[i]]);
	}

	cout << endl;

	ll ans = 0;
	FOR(i,0,n){
		if (realsus[i]==i) continue;
		ans++;
		ll amogus = sus[i];
		temp.push_back({i, sus[i]});

		swap(sus[realsus[i]], sus[i]);
		swap(realsus[i], realsus[amogus]);
	}
	if (ans<k){
		FOR(i,0,k-ans){
			temp.push_back({0,0});
		}
	}
	if (ans <= k) return 1;
	else return 0;
}

void genans(ll k){
	vector<ll> sus;
	unordered_map<ll, ll> realsus;

	FOR(i,0,n){
		sus.push_back(s[i]);
		realsus[s[i]] = i;
	}


	FOR(i,0,k){
		swap(realsus[sus[x[i]]], realsus[sus[y[i]]]);
		swap(sus[x[i]], sus[y[i]]);

		p[i] = realsus[temp[i][0]];
		q[i] = realsus[temp[i][1]];

		swap(sus[realsus[temp[i][0]]], sus[realsus[temp[i][1]]]);
		swap(realsus[temp[i][0]], realsus[temp[i][1]]);
	}
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	n = N;
	FOR(i,0,n){
		s[i] = S[i]; 
	}
	m = M;
	FOR(i,0,m){
		x[i] = X[i];
		y[i] = Y[i];
	}
	ll lo = 0;
	ll hi = n+1;

	while (lo<hi){
		int mid = lo + (hi - lo) / 2;
		if (check(mid)) {
			hi = mid;
		} else {
			lo = mid + 1;
		}
	}
	check(lo);
	genans(lo);
	FOR(i,0,lo){
		P[i] = p[i];
		Q[i] = q[i];
	}

	return lo;
}

Compilation message

sorting.cpp: In function 'void genans(int)':
sorting.cpp:54:24: warning: declaration of 'realsus' shadows a global declaration [-Wshadow]
   54 |  unordered_map<ll, ll> realsus;
      |                        ^~~~~~~
sorting.cpp:14:59: note: shadowed declaration is here
   14 | ll n,s[600001],m,x[600001],y[600001],p[600001],q[600001], realsus[600001];
      |                                                           ^~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 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 1 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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 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 1 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 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 2 ms 596 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 1 ms 596 KB Output is correct
26 Correct 1 ms 596 KB Output is correct
27 Correct 2 ms 596 KB Output is correct

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 656 KB Output is correct
2 Correct 4 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 1 ms 556 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 2 ms 516 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 4 ms 596 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 3 ms 596 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 335 ms 32044 KB Output is correct
16 Correct 409 ms 39056 KB Output is correct
17 Correct 479 ms 40708 KB Output is correct
18 Correct 101 ms 30276 KB Output is correct
19 Correct 259 ms 35240 KB Output is correct
20 Correct 285 ms 39404 KB Output is correct
21 Correct 292 ms 39708 KB Output is correct
22 Correct 337 ms 36744 KB Output is correct
23 Correct 383 ms 46052 KB Output is correct
24 Correct 445 ms 45580 KB Output is correct
25 Correct 419 ms 40948 KB Output is correct
26 Correct 278 ms 39452 KB Output is correct
27 Correct 277 ms 35492 KB Output is correct
28 Correct 433 ms 44792 KB Output is correct
29 Correct 362 ms 40028 KB Output is correct
30 Correct 216 ms 33848 KB Output is correct
31 Correct 383 ms 44324 KB Output is correct
32 Correct 340 ms 40712 KB Output is correct
33 Correct 486 ms 41372 KB Output is correct
34 Correct 425 ms 41264 KB Output is correct
35 Correct 298 ms 35008 KB Output is correct
36 Correct 90 ms 31868 KB Output is correct
37 Correct 428 ms 46556 KB Output is correct
38 Correct 482 ms 41216 KB Output is correct
39 Correct 435 ms 41288 KB Output is correct