Submission #785429

#	Time	Username	Problem	Language	Result	Execution time	Memory
785429		fatemetmhr	Sorting (IOI15_sorting)	C++17	56 / 100	60 ms	10360 KiB

sorting

//  ~ Be Name Khoda ~  //

#include "sorting.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  6000  + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;


int n, cmp, sz, pt, a[maxn5], b[maxn5], x[maxn5], y[maxn5];
int s1[maxn5], s2[maxn5];
bool mark[maxn5];

void sset(int a, int b){
	for(int i = sz - 1; i > pt; i--){
		if(a > b)
			swap(a, b);
		if(a == b || x[i] == y[i])
			continue;
		if((a == x[i] && b == y[i]) || (a != x[i] && a != y[i] && b != x[i] && b != y[i]))
			continue;
		if(a == x[i])
			a = y[i];
		else if(a == y[i])
			a = x[i];
		else if(b == x[i])
			b = y[i];
		else if(b == y[i])
			b = x[i];
	}
	s1[pt] = a;
	s2[pt] = b;
	pt++;
}

int rt;

void dfs(int v){
	mark[v] = true;
	if(!mark[b[v]]){
		//cout << "its " << v << ' ' << b[v] << endl;
		sset(rt, b[v]);
		dfs(b[v]);
	}
}

bool check(int m){
	//cout << "hereeeeee " << m << endl;
	sz = m;
	memset(mark, false, sizeof mark);
	for(int i = 0; i < n; i++){
		b[i] = a[i];
	}
	for(int i = 0; i < m; i++)
		swap(b[x[i]], b[y[i]]);
	pt = 0;
	for(int i = 0; i < n; i++) if(!mark[i]){
		rt = i;
		dfs(i);
	}
	//cout << "in " << m << ' ' << pt << endl;
	return pt <= m;
}



int findSwapPairs(int N, int A[], int m, int X[], int Y[], int p[], int q[]) {
	n = N;
	for(int i = 0; i < m; i++){
		x[i] = X[i];
		y[i] = Y[i];
		if(x[i] > y[i])
			swap(x[i], y[i]);
	}
	for(int i = 0; i < n; i++)
		a[i] = A[i];
	bool re = true;
	for(int i = 1; i < n; i++)
		re &= (a[i] > a[i - 1]);
	if(re)
		return 0;
    int lo = -1, hi = m;
    while(hi - lo > 1){
    	int mid = (hi + lo) >> 1;
    	if(check(mid))
    		hi = mid;
    	else
    		lo = mid;
    }
    check(hi);
	for(int i = 0; i < pt; i++){
		p[i] = s1[i];
		q[i] = s2[i];
	}
	for(int i = pt; i < hi; i++)
		p[i] = q[i] = 0;
    return hi;
}

Compilation message (stderr)

sorting.cpp: In function 'void sset(int, int)':
sorting.cpp:31:22: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   31 | void sset(int a, int b){
      |                  ~~~~^
sorting.cpp:27:31: note: shadowed declaration is here
   27 | int n, cmp, sz, pt, a[maxn5], b[maxn5], x[maxn5], y[maxn5];
      |                               ^
sorting.cpp:31:15: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   31 | void sset(int a, int b){
      |           ~~~~^
sorting.cpp:27:21: note: shadowed declaration is here
   27 | int n, cmp, sz, pt, a[maxn5], b[maxn5], x[maxn5], y[maxn5];
      |                     ^

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 0 / 18
• Subtask 5: 20 / 20
• Subtask 6: 0 / 26