oj.uz

Submission #794934

# Submission time Handle Problem Language Result Execution time Memory
794934 2023-07-27T04:12:24 Z Username4132 Sorting (IOI15_sorting) C++14
20 / 100
 1 ms 340 KB 
#include "sorting.h"
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using pii = pair<int, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define PB push_back
#define F first
#define S second

int n, cur;

vector<pii> gen(vector<int>& p){
	vector<int> q(n);
	forn(i, n) q[i]=p[i];
	vector<pii> ret;
	vector<bool> vis(n, false);
	forn(i, n) if(!vis[i]){
		vis[i]=true;
		int x=p[i];
		while(x!=i){
			vis[x]=true;
			ret.PB({q[i], q[x]});
			swap(q[i], q[x]);
			x=p[x];
		}
	}
	return ret;
}

void mov(vector<int>& per, int* X, int* Y, int pos){
	while(cur<pos){
		swap(per[X[cur]], per[Y[cur]]);
		++cur;
	}
	while(cur>pos){
		--cur;
		swap(per[X[cur]], per[Y[cur]]);
	}
}

int findSwapPairs(int N, int seq[], int M, int X[], int Y[], int P[], int Q[]) {
	n=N;
	vector<int> per(n);
	forn(i, n) per[i]=seq[i];


	int lo=-1, hi=n;
	while(hi-lo>1){
		int mid = (hi+lo)/2;
		mov(per, X, Y, mid);
		vector<pii> res = gen(per);
		if(res.size()>mid) lo=mid;
		else hi=mid;
	}

	vector<pii> res = gen(per);
	int ans = res.size();
	vector<int> inv(n);
	forn(i, n) inv[seq[i]]=i;

	forn(i, ans){
		int a = res[i].F, b = res[i].S;
		swap(inv[seq[X[i]]], inv[seq[Y[i]]]);
		swap(seq[X[i]], seq[Y[i]]);
		P[i]=inv[a], Q[i]=inv[b];
		swap(seq[P[i]], seq[Q[i]]);
		swap(inv[a], inv[b]);
	}
	return ans;
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:55:16: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |   if(res.size()>mid) lo=mid;
      |      ~~~~~~~~~~^~~~
sorting.cpp:60:20: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   60 |  int ans = res.size();
      |            ~~~~~~~~^~
sorting.cpp:44:41: warning: unused parameter 'M' [-Wunused-parameter]
   44 | int findSwapPairs(int N, int seq[], int M, int X[], int Y[], int P[], int Q[]) {
      |                                     ~~~~^

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 244 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 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Incorrect 0 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 244 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Incorrect 0 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 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 340 KB Output isn't correct
2 Halted 0 ms 0 KB -