oj.uz

Submission #65480

# Submission time Handle Problem Language Result Execution time Memory
65480 2018-08-07T17:41:34 Z hamzqq9 Sorting (IOI15_sorting) C++14
0 / 100
 6 ms 2048 KB 
#include "sorting.h"
#include<bits/stdc++.h>
using namespace std;
#define orta ((bas+son)>>1)
#define MAX 200005

int go[MAX],plc[MAX],_S[MAX],vis[MAX];

int get_val(int N) {

	int res=0;

	fill(vis,vis+N,0);

	for(int i=0;i<N;i++) {

		if(!vis[i]) {

			int cur=i;

			int sz=0;

			while(!vis[cur]) {

				vis[cur]=1;

				sz++;

				cur=go[cur];

			}

			res+=sz-1;

		}

	}
	
	return res;

}

void do_swap(int upto,int X[],int Y[]) {

	for(int i=0;i<upto;i++) swap(_S[X[i]],_S[Y[i]]);

}

void build_graph(int N) {

	for(int i=0;i<N;i++) plc[_S[i]]=i;

	for(int i=0;i<N;i++) go[plc[i]]=i;

}

bool okey(int N,int upto,int S[],int X[],int Y[]) {

	for(int i=0;i<N;i++) _S[i]=S[i];

	do_swap(upto,X,Y);
	
	build_graph(N);

	return get_val(N)<=upto;

}

void get_ans(int N,int upto,int P[],int Q[],int X[],int Y[],int S[]) {

	fill(vis,vis+N,0);

	int tot=0;

	pair<int,int> swp[MAX];

	for(int i=0;i<N;i++) {

		if(!vis[i]) {

			int cur=i;

			while(!vis[cur]) {

				vis[cur]=1;

				if(go[cur]!=i) {

					swp[tot++]={_S[cur],_S[go[cur]]};

				}

				cur=go[cur];

			}

		}

	}

	for(int i=0;i<N;i++) plc[S[i]]=i;

	for(int i=0;i<tot;i++) {

		swap(plc[S[X[i]]],plc[S[Y[i]]]);
		swap(S[X[i]],S[Y[i]]);

		P[i]=plc[swp[i].first];
		Q[i]=plc[swp[i].second];

	}

	while(tot<upto) {

		tot++;

		P[tot]=Q[tot]=0;

	}

}

void find_solution(int N,int upto,int S[],int X[],int Y[],int P[],int Q[]) {

	for(int i=0;i<N;i++) _S[i]=S[i];

	do_swap(upto,X,Y);

	build_graph(N);

	get_ans(N,upto,P,Q,X,Y,S);

}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    
	int bas=0,son=M;

	while(bas<=son) {

		if(okey(N,orta,S,X,Y)) son=orta-1;
		else bas=orta+1;

	}

	int ans=bas;

	find_solution(N,ans,S,X,Y,P,Q);

	return ans;

}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 20.0

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

Subtask #6
0 / 26.0

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