Submission #1185675

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185675		sano	Sorting (IOI15_sorting)	C++20	100 / 100	243 ms	10876 KiB

sorting

//#pragma GCC optimize("O3")
//#pragma GCC target("tune=native")
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include "sorting.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#include <cassert>
#include <bitset>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#define shit short int
#define ll long long
//#define int ll
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<int, int>
#define NEK 2000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize
#define prv1 47
#define prv2 43
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define all(x) (x).begin(), (x).end()
#define sig 0.0000001

using namespace std;
//using namespace __gnu_pbds;

//template <typename T1, typename T2>
//using indexed_set = tree<pair<T1, T2>, null_type, less<pair<T1, T2>>, rb_tree_tag, tree_order_statistics_node_update>;

bool najdi(int n, int s2[], int m, int x[], int y[], int p[], int q[]) {
	vec<int> s;
	For(i, n) s.push_back(s2[i]);


	vec<int> na_koho(n);
	For(i, n) na_koho[i] = i;
	rfor(i, m - 1) {
		swap(na_koho[x[i]], na_koho[y[i]]);
	}
	vec<int> teraz(n);
	For(i, n) teraz[s[i]] = i;
	int som = 0;
	vec<bool> vybaveny(n, false);
	int poc = 0;
	For(i, m) {
		swap(na_koho[x[i]], na_koho[y[i]]);
		swap(teraz[s[x[i]]], teraz[s[y[i]]]);
		swap(s[x[i]], s[y[i]]);
		bool mame = 0;
		while (som < n) {
			if (na_koho[teraz[som]] != som) {
				poc++;
				//vymen teraz[som], teraz[na_koho[teraz[som]]]
				if (vybaveny[na_koho[teraz[som]]]) {
					int lol = 1;
				}
				if (poc == 420) {
					int lol = 1;
				}
				vybaveny[na_koho[teraz[som]]] = 1;
				p[i] = teraz[som];
				q[i] = teraz[na_koho[teraz[som]]];
				swap(s[teraz[som]], s[teraz[na_koho[teraz[som]]]]);
				swap(teraz[som], teraz[na_koho[teraz[som]]]);
				mame = 1;
				break;
			}
			som++;
		}
		if (!mame) p[i] = q[i] = 0;
	}
	For(i, n) {
		if (s[i] != i) return 0;
	}
	return 1;
}

int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
	int l = 0, r = m;
	while (l < r) {
		int mid = (l + r) / 2;
		if (najdi(n, s, mid, x, y, p, q)) {
			r = mid;
		}
		else {
			l = mid + 1;
		}
	}
	najdi(n, s, l, x, y, p, q);
	return l;
}
/*
signed main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int t;
	t = 1;
	//cin >> t;
	For(i, t) {
		ifstream cin("09.in");
		ofstream cout("01.out");
		int n, m; cin >> n;
		int s[500], x[15000], y[15000], p[15000], q[15000];
		For(i, n) cin >> s[i];
		cin >> m;
		For(i, m) cin >> x[i] >> y[i];
		int r = findSwapPairs(n, s, m, x, y, p, q);
		cout << r << '\n';
		For(i, r) {
			cout << p[i] << ' ' << q[i] << '\n';
		}
	}
	return 0;
}*/

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