oj.uz

Submission #133649

# Submission time Handle Problem Language Result Execution time Memory
133649 2019-07-21T07:39:34 Z Mahdi_Jfri Sorting (IOI15_sorting) C++14
100 / 100
 532 ms 32600 KB 
#include "sorting.h"
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back

const int maxn = 2e5 + 20;
const int maxm = 3 * maxn;

int pos[maxn] , src[maxn] , a[maxn];
int p[maxm] , q[maxm] , x[maxm] , pp[maxn] , y[maxm] , n;

vector<int> shit;

bool check(int m)
{
	memcpy(a , src , sizeof src);
	if(!m)
	{
		bool f = 1;
		for(int i = 0; i < n; i++)
			f &= a[i] == i;
		return f;
	}

	swap(a[x[0]] , a[y[0]]);
	for(int i = 0; i < n; i++)
		pos[i] = i , shit.pb(i);

	for(int i = m - 1; i > 0; i--)
		swap(pos[x[i]] , pos[y[i]]);

	for(int i = 0; i < n; i++)
		pp[a[i]] = i;

	int pt = 0;
	for(int i = 0; i < m; i++)
	{
		p[i] = 0 , q[i] = 0;
		while(!shit.empty())
		{
			int j = shit.back();
			shit.pop_back();
			if(pos[j] != a[j])
			{
				int ind = pp[pos[j]];
				swap(a[ind] , a[j]);
				p[i] = ind , q[i] = j;
				swap(pp[a[ind]] , pp[a[j]]);
				break;
			}
		}

		if(i + 1 < m)
		{
			shit.pb(x[i + 1]);
			shit.pb(y[i + 1]);
			swap(pp[a[x[i + 1]]] , pp[a[y[i + 1]]]);
			swap(a[x[i + 1]] , a[y[i + 1]]);
			swap(pos[x[i + 1]] , pos[y[i + 1]]);
		}
	}

	bool f = 1;
	for(int i = 0; i < n; i++)
		f &= a[i] == i;
	return f;
}

int findSwapPairs(int N, int A[], int m, int X[], int Y[], int P[], int Q[])
{
	n = N;
	for(int i = 0; i < n; i++)
		src[i] = A[i];

	for(int i = 0; i < m; i++)
		x[i] = X[i] , y[i] = Y[i];

	int l = 0 , r = m;
	if(check(l))
		return l;

	while(r - l > 1)
	{
		int m = (l + r) / 2;
		if(check(m))
			r = m;
		else
			l = m;
	}

	check(r);
	for(int i = 0; i < r; i++)
		P[i] = p[i] , Q[i] = q[i];
	return r;
}

Compilation message

sorting.cpp: In function 'bool check(int)':
sorting.cpp:38:6: warning: unused variable 'pt' [-Wunused-variable]
  int pt = 0;
      ^~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:87:7: warning: declaration of 'int m' shadows a parameter [-Wshadow]
   int m = (l + r) / 2;
       ^
sorting.cpp:72:39: note: shadowed declaration is here
 int findSwapPairs(int N, int A[], int m, int X[], int Y[], int P[], int Q[])
                                       ^

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

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

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1272 KB Output is correct
2 Correct 5 ms 1400 KB Output is correct
3 Correct 5 ms 1400 KB Output is correct
4 Correct 3 ms 1272 KB Output is correct
5 Correct 5 ms 1400 KB Output is correct
6 Correct 5 ms 1528 KB Output is correct
7 Correct 5 ms 1400 KB Output is correct
8 Correct 6 ms 1400 KB Output is correct
9 Correct 5 ms 1400 KB Output is correct
10 Correct 6 ms 1400 KB Output is correct
11 Correct 5 ms 1400 KB Output is correct
12 Correct 5 ms 1528 KB Output is correct
13 Correct 6 ms 1400 KB Output is correct
14 Correct 4 ms 1272 KB Output is correct
15 Correct 281 ms 18928 KB Output is correct
16 Correct 339 ms 19344 KB Output is correct
17 Correct 532 ms 21224 KB Output is correct
18 Correct 47 ms 11256 KB Output is correct
19 Correct 295 ms 20960 KB Output is correct
20 Correct 346 ms 32600 KB Output is correct
21 Correct 345 ms 32556 KB Output is correct
22 Correct 281 ms 20612 KB Output is correct
23 Correct 305 ms 23392 KB Output is correct
24 Correct 524 ms 21544 KB Output is correct
25 Correct 518 ms 21352 KB Output is correct
26 Correct 319 ms 19320 KB Output is correct
27 Correct 260 ms 18520 KB Output is correct
28 Correct 439 ms 20584 KB Output is correct
29 Correct 475 ms 20528 KB Output is correct
30 Correct 204 ms 18280 KB Output is correct
31 Correct 484 ms 21052 KB Output is correct
32 Correct 311 ms 20204 KB Output is correct
33 Correct 527 ms 21564 KB Output is correct
34 Correct 380 ms 20432 KB Output is correct
35 Correct 313 ms 25348 KB Output is correct
36 Correct 95 ms 18028 KB Output is correct
37 Correct 524 ms 22096 KB Output is correct
38 Correct 519 ms 21172 KB Output is correct
39 Correct 511 ms 22160 KB Output is correct