Submission #785461

#	Time	Username	Problem	Language	Result	Execution time	Memory
785461		fatemetmhr	Sorting (IOI15_sorting)	C++17	100 / 100	146 ms	19944 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 =  6e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;


int n, a[maxn5], b[maxn5], x[maxn5], y[maxn5];
int mask[maxn5], rev[maxn5];
bool mark[maxn5], add = false;
vector <pair<int, int>> op;


int rt;

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

bool check(int m){
	//cout << "hereeeeee " << m << endl;
	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]]);
	int ans = n;
	for(int i = 0; i < n; i++) if(!mark[i]){
		rt = i;
		dfs(i);
		ans--;
	}
	//cout << "in " << m << ' ' << pt << endl;
	return ans <= 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;
    }
    add = true;
    check(hi);
    for(int i = 0; i < n; i++)
    	mask[i] = rev[i] = i;
    for(int i = 0; i < hi; i++)
    	q[i] = p[i] = 0;
    for(int i = hi - 1; i >= 0; i--){
    	if(op.size() > i){
    		p[i] = mask[op.back().fi];
    		q[i] = mask[op.back().se];
    		op.pop_back();
    	}
    	int a = rev[x[i]], b = rev[y[i]];
    	mask[a] = y[i];
    	mask[b] = x[i];
    	rev[x[i]] = b;
    	rev[y[i]] = a;
    }
    return hi;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:95:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   95 |      if(op.size() > i){
      |         ~~~~~~~~~~^~~
sorting.cpp:100:10: warning: declaration of 'a' shadows a global declaration [-Wshadow]
  100 |      int a = rev[x[i]], b = rev[y[i]];
      |          ^
sorting.cpp:27:8: note: shadowed declaration is here
   27 | int n, a[maxn5], b[maxn5], x[maxn5], y[maxn5];
      |        ^
sorting.cpp:100:25: warning: declaration of 'b' shadows a global declaration [-Wshadow]
  100 |      int a = rev[x[i]], b = rev[y[i]];
      |                         ^
sorting.cpp:27:18: note: shadowed declaration is here
   27 | int n, a[maxn5], b[maxn5], x[maxn5], y[maxn5];
      |                  ^

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