Submission #295181

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
295181	2020-09-09T14:09:00 Z	shivensinha4	Kralj (COCI16_kralj)	C++17	140 / 140	798 ms	43624 KB

kralj

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h> 
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
//#define endl '\n'


int main() {
	#ifdef shiven
	freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n; cin >> n;
	vi a(n), b(n), advPref(n);
	vector<vi> elfHere(n);
	for_(i, 0, n) {
		int k; cin >> k;
		k -= 1;
		advPref[k] += 1;
		elfHere[k].push_back(i);
	}
	for_(i, 0, n) cin >> a[i];
	for_(i, 0, n) cin >> b[i];
	
	int mn = INT_MAX, mnIdx = -1;
	for_(i, 0, n) {
		if (i > 0) advPref[i] += advPref[i-1];
		if (advPref[i]-i < mn) {
			mn = advPref[i]-i;
			mnIdx = i;
		}
	}

	//cout << "mn: " << mnIdx << endl;
	mnIdx += 1;
	int ans = 0;
	set<int> s;
	for_(idx, 0, n) {
		int i = (mnIdx + idx);
		if (i >= n) i -= n;
		for (auto j: elfHere[i]) s.insert(b[j]);
		auto pt = s.lower_bound(a[i]);
		if (pt == s.end()) {
			s.erase(s.begin());
		} else {
			ans += 1;
			s.erase(pt);
		}
	}
	
	cout << ans << endl;

	return 0;
}

Compilation message

kralj.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
kralj.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	798 ms	35184 KB	Output is correct
2	Correct	474 ms	34156 KB	Output is correct
3	Correct	595 ms	42480 KB	Output is correct
4	Correct	587 ms	43624 KB	Output is correct
5	Correct	389 ms	19704 KB	Output is correct
6	Correct	346 ms	20220 KB	Output is correct
7	Correct	469 ms	23288 KB	Output is correct
8	Correct	384 ms	21752 KB	Output is correct
9	Correct	491 ms	24440 KB	Output is correct
10	Correct	399 ms	21880 KB	Output is correct