Submission #1013365

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013365		d4xn	Teams (IOI15_teams)	C++17	21 / 100	235 ms	524288 KiB

teams

#pragma GCC optimize ("Ofast")
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 100000, S = 316;

int n;
pair<int, int> sg[N];
vector<pair<int, int>> lp[N];
bitset<N> curr, temp, bt[N], pre[S];

void init(int nn, int a[], int b[]) {
	n = nn;
	for (int i = 0; i < n; i++) {
		sg[i] = make_pair(b[i], a[i]);
	}
	sort(sg, sg+n);

	for (int i = 0; i < n; i++) {
		lp[sg[i].second].push_back(make_pair(sg[i].first, i));
	}

	priority_queue<pair<int, int>> pq;
	for (int i = 1; i <= n; i++) {
		for (auto& [j, idx] : lp[i]) {
			pq.push(make_pair(-j, idx));
			curr[idx] = 1;
		}

		bt[i] = curr;

		while (!pq.empty() && -pq.top().first <= i) {
			curr[pq.top().second] = 0;
			pq.pop();
		}
	}

	pre[0].reset();
	for (int i = 1; i < S; i++) {
		pre[i] = pre[i-1];
		for (int j = S*(i-1); j < S*i; j++) {
			pre[i][j] = 1;
		}
	}
}

int can(int m, int k[]) {
	sort(k, k+m);

	curr = pre[S-1];
	for (int i = S*(S-1); i <= n; i++) {
		curr[i] = 1;
	}

	for (int i = 0; i < m; i++) {
		temp = (curr & bt[k[i]]);
		if (((int)temp.count()) < k[i]) return 0;

		// solo quiero los k primeros de temp
		int l = 0;
		int r = n-1;
		while (l < r) {
			int mid = (l+r) >> 1;

			int block = mid/S;
			for (int j = S*block; j <= mid; j++) {
				pre[block][j] = 1;
			}

			if (((int)(temp & pre[block]).count()) >= k[i]) r = mid;
			else l = mid+1;

			for (int j = S*block; j <= mid; j++) {
				pre[block][j] = 0;
			}
		}

		// le quito a curr los k primeros de temp
		int block = l/S;
		for (int j = S*block; j <= l; j++) {
			pre[block][j] = 1;
		}

		curr ^= (temp & pre[block]);

		for (int j = S*block; j <= l; j++) {
			pre[block][j] = 0;
		}
	}

	return 1;
}

/*
		cerr << i << endl;
		for (int j = 0; j < n; j++) {
			cerr << curr[j] << " ";
		}
		cerr << endl;

		cerr << k[i] << endl;
		for (int j = 0; j < n; j++) {
			cerr << bt[k[i]][j] << " ";
		}
		cerr << endl;

		temp = curr & bt[k[i]];
		cerr << (int)temp.count() << endl << endl;
		*/

• Subtask 1: 21 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23