oj.uz

Submission #393935

# Submission time Handle Problem Language Result Execution time Memory
393935 2021-04-25T01:07:33 Z arwaeystoamneg Sorting (IOI15_sorting) C++17
100 / 100
 445 ms 44036 KB 
// EXPLOSION!
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
#define endl '\n'
//#define ednl '\n'
#define test int testc;cin>>testc;while(testc--)
#define pr(a, b) trav(x,a)cerr << x << b; cerr << endl;
#define message cout << "Hello World" << endl;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 1000000007;//998244353    

void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
	F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef arwaeystoamneg
	if (sz(s))
	{
		freopen((s + ".in").c_str(), "r", stdin);
		if (s != "test1")
			freopen((s + ".out").c_str(), "w", stdout);
	}
#endif
}
#ifndef arwaeystoamneg 
#include "sorting.h"
#endif
const int MAX = 200005;
int n, m, a[MAX], x[3 * MAX], y[3 * MAX], ne[MAX], v[MAX], temp[MAX];
vpi tempo;
vpi ans;
void dfs(int i)
{
	if (v[i])return;
	v[i] = 1;
	tempo.pb({ ne[i],i });
	dfs(ne[i]);
}
bool check()
{
	F0R(i, m)swap(a[x[i]], a[y[i]]);
	F0R(i, n)ne[a[i]] = i;
	fill(v, v + n, 0);
	int c = 0;
	F0R(i, n)
	{
		if (!v[i])
		{
			tempo.clear();
			c++, dfs(i);
			tempo.pop_back();
			reverse(all(tempo));
			trav(chess, tempo)ans.pb(chess);
		}
	}
	if (n - c > m)return 0;
	while (sz(ans) < m)ans.pb({ 0,0 });
	R0F(i, m)swap(a[x[i]], a[y[i]]);
	F0R(i, n)temp[a[i]] = i;
	vpi t;
	F0R(i, m)
	{
		swap(temp[a[x[i]]], temp[a[y[i]]]);
		swap(a[x[i]], a[y[i]]);
		int j = temp[ans[i].f], k = temp[ans[i].s];
		t.pb({ j,k });
		swap(temp[a[j]], temp[a[k]]);
		swap(a[j], a[k]);
	}
	ans = t;
	return 1;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) 
{
	n = N;
	int l = 0, r = M;
	F0R(i, min(3 * MAX, M))x[i] = X[i], y[i] = Y[i];
	while (l < r)
	{
		m = (l + r) / 2;
		F0R(i, n)a[i] = S[i];
		if (check())r = m;
		else l = m + 1;
		ans.clear();
	}
	m = l;
	F0R(i, n)a[i] = S[i];
	check();
	F0R(i, sz(ans))P[i] = ans[i].f, Q[i] = ans[i].s;
	return l;
}
#ifdef arwaeystoamneg
int main()
{
	setIO("");
	int N, M;
	cin >> N;
	int* S = (int*)malloc(sizeof(int) * (unsigned int)N);
	for (int i = 0; i < N; ++i)
		cin>>S[i];
	cin >> M;
	int* X = (int*)malloc(sizeof(int) * (unsigned int)M), * Y = (int*)malloc(sizeof(int) * (unsigned int)M);
	for (int i = 0; i < M; ++i) {
		cin >> X[i] >> Y[i];
	}
	int* P = (int*)malloc(sizeof(int) * (unsigned int)M), * Q = (int*)malloc(sizeof(int) * (unsigned int)M);
	int ans = findSwapPairs(N, S, M, X, Y, P, Q);
	cout << ans << endl;
	for (int i = 0; i < ans; ++i)
		cout << P[i] << " " << Q[i] << endl;
	F0R(i, ans)
	{
		swap(S[X[i]], S[Y[i]]);
		swap(S[P[i]], S[Q[i]]);
	}
	F0R(i, n)cout << S[i] << " ";
	return 0;
}


#endif

Compilation message

sorting.cpp: In function 'void setIO(std::string)':
sorting.cpp:30:11: warning: unused parameter 'second' [-Wunused-parameter]
   30 | #define s second
      |           ^
sorting.cpp:44:19: note: in expansion of macro 's'
   44 | void setIO(string s) {
      |                   ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 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 1 ms 332 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 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 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 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 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 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 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 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 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 304 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 2 ms 844 KB Output is correct
22 Correct 2 ms 844 KB Output is correct
23 Correct 2 ms 844 KB Output is correct
24 Correct 2 ms 844 KB Output is correct
25 Correct 2 ms 844 KB Output is correct
26 Correct 2 ms 844 KB Output is correct
27 Correct 2 ms 844 KB Output is correct

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 3 ms 716 KB Output is correct
3 Correct 3 ms 708 KB Output is correct
4 Correct 2 ms 668 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 3 ms 588 KB Output is correct
8 Correct 3 ms 716 KB Output is correct
9 Correct 3 ms 716 KB Output is correct
10 Correct 3 ms 716 KB Output is correct
11 Correct 3 ms 588 KB Output is correct
12 Correct 2 ms 716 KB Output is correct
13 Correct 3 ms 716 KB Output is correct
14 Correct 2 ms 588 KB Output is correct
15 Correct 340 ms 37300 KB Output is correct
16 Correct 345 ms 37728 KB Output is correct
17 Correct 413 ms 40904 KB Output is correct
18 Correct 186 ms 34596 KB Output is correct
19 Correct 317 ms 36980 KB Output is correct
20 Correct 303 ms 34992 KB Output is correct
21 Correct 293 ms 38048 KB Output is correct
22 Correct 331 ms 29768 KB Output is correct
23 Correct 414 ms 41900 KB Output is correct
24 Correct 402 ms 41708 KB Output is correct
25 Correct 392 ms 40588 KB Output is correct
26 Correct 316 ms 30896 KB Output is correct
27 Correct 300 ms 30384 KB Output is correct
28 Correct 391 ms 39644 KB Output is correct
29 Correct 374 ms 30908 KB Output is correct
30 Correct 236 ms 30596 KB Output is correct
31 Correct 411 ms 31588 KB Output is correct
32 Correct 369 ms 40248 KB Output is correct
33 Correct 419 ms 41488 KB Output is correct
34 Correct 399 ms 31788 KB Output is correct
35 Correct 327 ms 35288 KB Output is correct
36 Correct 151 ms 30512 KB Output is correct
37 Correct 440 ms 44036 KB Output is correct
38 Correct 417 ms 43116 KB Output is correct
39 Correct 445 ms 42664 KB Output is correct