oj.uz

Submission #1065144

# Submission time Handle Problem Language Result Execution time Memory
1065144 2024-08-19T00:52:02 Z pawned Sorting (IOI15_sorting) C++17
0 / 100
 1 ms 348 KB 
#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

#include "sorting.h"

int countcyc(vi perm) {
	int N = perm.size();
	vector<bool> vis(N, false);
	int res = 0;
	for (int i = 0; i < N; i++) {
		if (!vis[i]) {
			vis[i] = true;
			int curr = perm[i];
			while (curr != i) {
				vis[curr] = true;
				curr = perm[curr];
			}
			res++;
		}
	}
	return res;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	vi start;
	for (int i = 0; i < N; i++) {
		start.pb(S[i]);
	}
//	cout<<"cycs: "<<countcyc(start)<<endl;
	int low = 0;
	int high = M;
	int ans = -1;	// minimum number of moves so can sort
	while (low <= high) {	// false, false, false, true, true, true
		int mid = (low + high) / 2;
		vi perm = start;
		for (int j = 0; j < mid; j++) {
			swap(perm[X[j]], perm[Y[j]]);
		}
		if ((N - countcyc(perm)) <= mid) {
			ans = mid;
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}
//	cout<<"ans: "<<ans<<endl;
	// take note of what to swap
	vi perm = start;
	for (int j = 0; j < ans; j++) {
		swap(perm[X[j]], perm[Y[j]]);
	}
/*	cout<<"perm: ";
	for (int x : perm)
		cout<<x<<" ";
	cout<<endl;*/
	// find all cycles, then values to swap
	vector<ii> allp;
	vector<bool> vis(N, false);
	for (int i = 0; i < N; i++) {
		if (!vis[i]) {
			vis[i] = true;
			int curr = perm[i];
			if (perm[curr] == curr)
				continue;
			allp.pb({curr, perm[curr]});
			while (curr != i) {
				vis[curr] = true;
				if (perm[curr] != i)
					allp.pb({curr, perm[curr]});
				curr = perm[curr];
			}
		}
	}
/*	cout<<"allp: ";
	for (ii p : allp)
		cout<<"("<<p.fi<<", "<<p.se<<"); ";
	cout<<endl;*/
	// convert vals to swap -> indices to swap
	vi pos(N, -1);
	for (int i = 0; i < N; i++) {
		pos[start[i]] = i;
	}
	vi cpr = start;	// current perm
	vector<ii> moves;
	int K = allp.size();
	for (int i = 0; i < K; i++) {
		int p1 = pos[cpr[X[i]]];
		int p2 = pos[cpr[Y[i]]];
		pos[cpr[X[i]]] = p2;
		pos[cpr[Y[i]]] = p1;
		swap(cpr[X[i]], cpr[Y[i]]);
		moves.pb({pos[allp[i].fi], pos[allp[i].se]});
	}
	for (int i = 0; i < ans - K; i++) {
		moves.pb({0, 0});
	}
/*	cout<<"moves: ";
	for (ii p : moves)
		cout<<"("<<p.fi<<", "<<p.se<<"); ";
	cout<<endl;*/
	for (int i = 0; i < ans; i++) {
		P[i] = moves[i].fi;
		Q[i] = moves[i].se;
	}
	return ans;
}

Compilation message

sorting.cpp: In function 'int countcyc(vi)':
sorting.cpp:16:19: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   16 |  int N = perm.size();
      |          ~~~~~~~~~^~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:95:19: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   95 |  int K = allp.size();
      |          ~~~~~~~~~^~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 20.0

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

Subtask #6
0 / 26.0

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