oj.uz

Submission #138314

# Submission time Handle Problem Language Result Execution time Memory
138314 2019-07-29T18:09:26 Z Sorting Sorting (IOI15_sorting) C++14
0 / 100
 8 ms 380 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 7;

int n, m;
int *s, *x, *y, *p, *q;
int tmp[N], tmp2[N], where[N];
bool used[N];

int timer = 0;

int dfs(int u){
	used[u] = true;

	int cnt = 1;

	if(!used[ tmp[u] ]){
		cnt += dfs(tmp[u]);
	}

	return cnt;
}

void make_swap(int l, int r){
	swap(tmp2[l], tmp2[r]);
	swap(where[ tmp2[l] ], where[ tmp2[r] ]);
}

void dfs_ans (int u){
	used[u] = true;

	if(!used[ tmp[u] ]){
		dfs(tmp[u]);

		make_swap(x[timer], y[timer]);

		p[timer] = where[ tmp[u] ];
		q[timer] = where[ tmp[tmp[u]] ];

		swap(tmp[u], tmp[tmp[u]]);

		make_swap(p[timer], q[timer]);

		++timer;
	}
}

bool check(int mid){
	for(int i = 0; i < n; i++){
		tmp[i] = s[i]; 
		used[i] = false;
	}

	for(int i = 0; i < mid; i++){
		swap(tmp[ x[i] ], tmp[ y[i] ]);
	}

	int cnt = 0;

	for(int i = 0; i < n; i++){
		if(!used[i]){
			cnt += dfs(i) - 1;
		}
	}

	return (cnt <= mid);
}

void find_ans(int mid){
	for(int i = 0; i < n; i++){
		tmp[i] = s[i]; 
		tmp2[i] = s[i];
		where[s[i]] = i;
		used[i] = false;
	}

	for(int i = 0; i < mid; i++){
		swap(tmp[ x[i] ], tmp[ y[i] ]);
		//swap(where[ s[x[i]] ], where[ s[y[i]] ]);
	}

	int cnt = 0;

	for(int i = 0; i < n; i++){
		if(!used[i]){
			dfs_ans(i);
		}
	}

	while(timer < mid){
		p[timer] = 0;
		q[timer++] = 0;
	}
}

int findSwapPairs(int _n, int _s[], int _m, int _x[], int _y[], int _p[], int _q[]){
	n = _n, s = _s, m = _m, x = _x, y = _y, p = _p, q = _q;

	int l = 0, r = m;

	while(l != r){
		int mid = (l + r) >> 1;

		if(check(mid)){
			r = mid;
		}
		else{
			l = mid + 1;
		}
	}

	find_ans(l);

	return l;
}

Compilation message

sorting.cpp: In function 'void find_ans(int)':
sorting.cpp:84:6: warning: unused variable 'cnt' [-Wunused-variable]
  int cnt = 0;
      ^~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Incorrect 2 ms 376 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Incorrect 2 ms 376 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Incorrect 2 ms 376 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -