Submission #684786

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
684786	2023-01-22T13:11:06 Z	LeonaRaging	Kralj (COCI16_kralj)	C++14	140 / 140	509 ms	54948 KB

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

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.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	509 ms	47204 KB	Output is correct
2	Correct	306 ms	45988 KB	Output is correct
3	Correct	396 ms	54328 KB	Output is correct
4	Correct	401 ms	54948 KB	Output is correct
5	Correct	288 ms	34200 KB	Output is correct
6	Correct	249 ms	33856 KB	Output is correct
7	Correct	335 ms	37992 KB	Output is correct
8	Correct	277 ms	36088 KB	Output is correct
9	Correct	361 ms	39328 KB	Output is correct
10	Correct	269 ms	35788 KB	Output is correct