Official

C - Cards Query Problem Editorial by en_translator


In this editorial, a query in the \(i\)-th format is denoted query \(i\).
We maintain arrays \(box_1, box_2, \ldots, box_N\) and \(card_1, card_2, \ldots, card_{200000}\). \(box_i\) manages the mulitset of cards in box \(i\), and \(card_i\) manages the box numbers that contain cards with \(i\).
For query \(1\), insert \(j\) to \(card_i\) and \(i\) to \(box_j\). This can be done in an \(\mathrm{O} (1)\) time.
For query \(2\), sort in ascending order the contents of the object (\(box_i\)) of the query and print them. For query \(3\), also remove duplicating elements. This can be done in a total of \(\mathrm{O} (S\log S)\) time over all queries, where \(S\) is the number of elements to be printed. Since \(S \leq 200000\), it is fast enough.
Note that sorting the elements for each query may result in TLE (Time Limit Exceeded). (What if queries 1 1 1 are given many times?)

Sample code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 200010;
const int M = 200010;
vector<vector<int>> box(N, vector<int>());
vector<vector<int>> card(M, vector<int>());

int main() {
	int n, q;
	cin >> n >> q;
	vector<vector<int>> ans;
	while (q--) {
		int t;
		cin >> t;
		if (t == 1) {
			int i, j;
			cin >> i >> j;
			card[i].push_back(j);
			box[j].push_back(i);
		}
		else if (t == 2) {
			int i;
			cin >> i;
			sort(box[i].begin(), box[i].end());
			for (int j = 0; j < box[i].size(); j++) {
				cout << box[i][j] << "\n "[j + 1 != box[i].size()];
			}
		}
		else {
			int i;
			cin >> i;
			sort(card[i].begin(), card[i].end());
			card[i].erase(unique(card[i].begin(), card[i].end()), card[i].end());
			for (int j = 0; j < card[i].size(); j++) {
				cout << card[i][j] << "\n "[j + 1 != card[i].size()];
			}
		}
	}
}

posted:
last update: