Submission #544504

#	Time	Username	Problem	Language	Result	Execution time	Memory
544504		model_code	Team Contest (JOI22_team)	C++17	100 / 100	138 ms	3980 KiB

team

/*
	[ SAMPLE SOURCE CODE FOR "TEAM CONTEST" ]
	Algorithm: Please refer to the editorial.
	Time Complexity: O(N log N)
*/

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

int main() {
	// step #1. read input
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N;
	cin >> N;
	vector<int> X(N), Y(N), Z(N);
	for (int i = 0; i < N; i++) {
		cin >> X[i] >> Y[i] >> Z[i];
	}
	
	// step #2. erase from the top
	vector<int> px(N), py(N), pz(N);
	for (int i = 0; i < N; i++) {
		px[i] = i;
		py[i] = i;
		pz[i] = i;
	}
	sort(px.begin(), px.end(), [&](int i, int j) { return X[i] < X[j]; });
	sort(py.begin(), py.end(), [&](int i, int j) { return Y[i] < Y[j]; });
	sort(pz.begin(), pz.end(), [&](int i, int j) { return Z[i] < Z[j]; });
	vector<bool> used(N, false);
	int tx = N - 1, ty = N - 1, tz = N - 1;
	bool found = false;
	while (tx != -1 && ty != -1 && tz != -1) {
		int mx = X[px[tx]], my = Y[py[ty]], mz = Z[pz[tz]];
		int cntx = 1 + (Y[px[tx]] == my ? 1 : 0) + (Z[px[tx]] == mz ? 1 : 0);
		int cnty = 1 + (Z[py[ty]] == mz ? 1 : 0) + (X[py[ty]] == mx ? 1 : 0);
		int cntz = 1 + (X[pz[tz]] == mx ? 1 : 0) + (Y[pz[tz]] == my ? 1 : 0);
		if (cntx >= 2) {
			used[px[tx]] = true;
			tx--;
		}
		else if (cnty >= 2) {
			used[py[ty]] = true;
			ty--;
		}
		else if (cntz >= 2) {
			used[pz[tz]] = true;
			tz--;
		}
		else {
			cout << mx + my + mz << endl;
			found = true;
			break;
		}
		while (tx != -1 && used[px[tx]]) tx--;
		while (ty != -1 && used[py[ty]]) ty--;
		while (tz != -1 && used[pz[tz]]) tz--;
	}
	if (!found) {
		cout << -1 << endl;
	}
	
	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 27 / 27