Submission #684786

#	Time	Username	Problem	Language	Result	Execution time	Memory
684786		LeonaRaging	Kralj (COCI16_kralj)	C++14	140 / 140	509 ms	54948 KiB

kralj

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define db(val) "[" #val " = " << (val) << "] "

const int maxn = 5e5 + 4;

int n, p[maxn], q[maxn], Rank[maxn], par[maxn];
vector<int> own[maxn];

int find(int x) {
	if (x != par[x]) par[x] = find(par[x]);
	return par[x];
}

bool join(int u, int v) {
	u = find(u); v = find(v);
	if (u == v) return 0;
	Rank[u] += Rank[v];
	par[v] = u;
	return 1;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 0, x; i < n; i++) {
    	cin >> x; x--;
    	own[x].pb(i);
    }
    for (int i = 0; i < n; i++) {
    	cin >> p[i];
    	Rank[i] = own[i].size();
    	par[i] = i;
    }
    for (int i = 0; i < n; i++)	
    	cin >> q[i];
    for (int i = 0; i < n; i++)
    	if (i == find(i))
    		for (int j = 1; j < Rank[i]; j++)
    			join(i, (i + j) % n);
	set<int> mySet; 
	int res = 0;
	for (int i = 0; i < n; i++) if (i == find(i)) {
		mySet.clear();
		for (int j = 0; j < Rank[i]; j++) {
			int x = (i + j) % n;
			for (int k : own[x])
				mySet.insert(q[k]);
			auto it = mySet.lower_bound(p[x]);
			if (it != mySet.end())
				res++, mySet.erase(it);
			else mySet.erase(mySet.begin());
		}
	}
	cout << res;
}

Compilation message (stderr)

kralj.cpp: In function 'int main()':
kralj.cpp:41:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   41 |     for (int i = 0; i < n; i++)
      |     ^~~
kralj.cpp:45:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   45 |  set<int> mySet;
      |  ^~~

• Subtask 1: 140 / 140