oj.uz

Submission #96889

# Submission time Handle Problem Language Result Execution time Memory
96889 2019-02-12T15:49:21 Z figter001 Sorting (IOI15_sorting) C++14
0 / 100
 3 ms 512 KB 
#include "sorting.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 2e5+50;

vector<int> a;
vector<pair<int,int>> s;
int idx[maxn];

bool can(int md){
	vector<int> b = a;
	for(int i=0;i<md;i++)
		swap(b[s[i].first],b[s[i].second]);
	int cnt = 0;
	for(int i=0;i<a.size();i++){
		while(b[i] != i){
			cnt ++;
			swap(b[i],b[b[i]]);
		}
	}
	return cnt <= md;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    for(int i=0;i<N;i++)a.push_back(S[i]);
    for(int i=0;i<M;i++)s.push_back({X[i],Y[i]});
    int md,lo=0,hi = M,ans;
	while(lo <= hi){
		md = (lo + hi)/2;
		if(can(md)){
			hi = md-1;
			ans = md;
		}else lo = md+1;
	}
	for(int i=0;i<ans;i++)swap(a[s[i].first],a[s[i].second]);
	vector<pair<int,int>> c;
	vector<int> b = a;
	for(int i=0;i<a.size();i++){
		while(a[i] != i){
			c.push_back({i,a[i]});
			swap(a[i],a[a[i]]);
		}
	}
	a = b;
	while(c.size() < md)c.push_back({0,0});
	for(int i=0;i<N;i++)idx[a[i]] = i;
	for(int i=0;i<ans;i++){
		int l = s[i].first;
		int r = s[i].second;
		swap(idx[a[l]],idx[a[r]]);
		swap(a[l],a[r]);
		l = c[i].first;
		r = c[i].second;
		P[i] = idx[l];
		Q[i] = idx[r];
		swap(a[P[i]],a[Q[i]]);
		swap(idx[l],idx[r]);
	}
	return ans;
}

Compilation message

sorting.cpp: In function 'bool can(int)':
sorting.cpp:18:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a.size();i++){
              ~^~~~~~~~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:41:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a.size();i++){
              ~^~~~~~~~~
sorting.cpp:48:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(c.size() < md)c.push_back({0,0});
        ~~~~~~~~~^~~~
sorting.cpp:30:24: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int md,lo=0,hi = M,ans;
                        ^~~
sorting.cpp:48:17: warning: 'md' may be used uninitialized in this function [-Wmaybe-uninitialized]
  while(c.size() < md)c.push_back({0,0});
        ~~~~~~~~~^~~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Incorrect 3 ms 384 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 512 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 512 KB Output isn't correct
2 Halted 0 ms 0 KB -