oj.uz

Submission #785460

# Submission time Handle Problem Language Result Execution time Memory
785460 2023-07-17T09:19:43 Z fatemetmhr Sorting (IOI15_sorting) C++17
74 / 100
 39 ms 10660 KB 
//  ~ Be Name Khoda ~  //

#include "sorting.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  15000  + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;


int n, a[maxn5], b[maxn5], x[maxn5], y[maxn5];
int mask[maxn5], rev[maxn5];
bool mark[maxn5], add = false;
vector <pair<int, int>> op;


int rt;

void dfs(int v){
	mark[v] = true;
	if(!mark[b[v]]){
		//cout << "its " << v << ' ' << b[v] << endl;
		if(add)
			op.pb({rt, b[v]});
		dfs(b[v]);
	}
}

bool check(int m){
	//cout << "hereeeeee " << m << endl;
	memset(mark, false, sizeof mark);
	for(int i = 0; i < n; i++){
		b[i] = a[i];
	}
	for(int i = 0; i < m; i++)
		swap(b[x[i]], b[y[i]]);
	int ans = n;
	for(int i = 0; i < n; i++) if(!mark[i]){
		rt = i;
		dfs(i);
		ans--;
	}
	//cout << "in " << m << ' ' << pt << endl;
	return ans <= m;
}



int findSwapPairs(int N, int A[], int m, int X[], int Y[], int p[], int q[]) {
	n = N;
	for(int i = 0; i < m; i++){
		x[i] = X[i];
		y[i] = Y[i];
		if(x[i] > y[i])
			swap(x[i], y[i]);
	}
	for(int i = 0; i < n; i++)
		a[i] = A[i];
	bool re = true;
	for(int i = 1; i < n; i++)
		re &= (a[i] > a[i - 1]);
	if(re)
		return 0;
    int lo = -1, hi = m;
    while(hi - lo > 1){
    	int mid = (hi + lo) >> 1;
    	if(check(mid))
    		hi = mid;
    	else
    		lo = mid;
    }
    add = true;
    check(hi);
    for(int i = 0; i < n; i++)
    	mask[i] = rev[i] = i;
    for(int i = 0; i < hi; i++)
    	q[i] = p[i] = 0;
    for(int i = hi - 1; i >= 0; i--){
    	if(op.size() > i){
    		p[i] = mask[op.back().fi];
    		q[i] = mask[op.back().se];
    		op.pop_back();
    	}
    	int a = rev[x[i]], b = rev[y[i]];
    	mask[a] = y[i];
    	mask[b] = x[i];
    	rev[x[i]] = b;
    	rev[y[i]] = a;
    }
    return hi;
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:95:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   95 |      if(op.size() > i){
      |         ~~~~~~~~~~^~~
sorting.cpp:100:10: warning: declaration of 'a' shadows a global declaration [-Wshadow]
  100 |      int a = rev[x[i]], b = rev[y[i]];
      |          ^
sorting.cpp:27:8: note: shadowed declaration is here
   27 | int n, a[maxn5], b[maxn5], x[maxn5], y[maxn5];
      |        ^
sorting.cpp:100:25: warning: declaration of 'b' shadows a global declaration [-Wshadow]
  100 |      int a = rev[x[i]], b = rev[y[i]];
      |                         ^
sorting.cpp:27:18: note: shadowed declaration is here
   27 | int n, a[maxn5], b[maxn5], x[maxn5], y[maxn5];
      |                  ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 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 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 292 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 352 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 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 292 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 352 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 596 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 488 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 1 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 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 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 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Runtime error 39 ms 10660 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -