CSES - Datatähti Open 2017 - Results
Submission details
Task:Family reunion
Sender:koosaga
Submission time:2023-01-02 18:23:21 +0200
Language:C++ (C++17)
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED19
#2ACCEPTED32
#3ACCEPTED49
Test results
testverdicttimegroup
#1ACCEPTED0.10 s1details
#2ACCEPTED0.13 s2details
#3ACCEPTED2.53 s3details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:29:29: warning: unused variable 'mx' [-Wunused-variable]
   29 |                         int mx = *max_element(all(ord)) + 1;
      |                             ^~

Code

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<lint, 2>;
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
const int MAXN = 2000005;
const int MAXA = 26;

int binom(int u, int v) {
	int ans = 1;
	for (int i = 1; i <= v; i++)
		ans *= u + 1 - i, ans /= i;
	return ans;
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m, k;
	cin >> n >> m >> k;
	for (int i = 0; i < m; i++) {
		vector<int> ord(2 * k + 1);
		for (int j = 0; j < sz(ord); j++)
			cin >> ord[j], ord[j]--;
		ord.resize(7);
		for (int i = 7; i >= 4; i--) {
			vector<int> nord;
			int mx = *max_element(all(ord)) + 1;
			if (i == 7) {
				for (int j = 0; j < sz(ord) - 1; j++) {
					int u = ord[j], v = ord[j + 1];
					int i = 0;
					while (((u ^ v) >> i) % 2 == 0)
						i++;
					nord.push_back(2 * i + (u >> i) % 2);
				}
			} else {
				int k = (i == 6 ? 12 : (i == 5 ? 6 : 4)) / 2;
				vector<int> cand;
				for (int i = 0; i < (1 << (2 * k)); i++) {
					if (__builtin_popcount(i) == k)
						cand.push_back(i);
				}
				for (int j = 0; j < sz(ord) - 1; j++) {
					int u = ord[j], v = ord[j + 1];
					u = cand[u], v = cand[v];
					int i = 0;
					while ((u >> i) % 2 == 1 || (v >> i) % 2 == 0)
						i++;
					nord.push_back(i);
				}
			}

			for (int i = 1; i < sz(nord); i++)
				assert(nord[i - 1] != nord[i]);
			ord = nord;
		}
		if (ord[1] < 3)
			cout << (char)(ord[1] + 'A') << "\n";
		else {
			int u = 0;
			while (ord[0] == u || ord[2] == u)
				u++;
			cout << (char)(u + 'A') << "\n";
		}
	}
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
#!/bin/bash
set -e
OFFSET=$(grep -onam1 '^__DATA_...

correct output
50

user output
A

B

A
...
Truncated

Test 2

Group: 2

Verdict: ACCEPTED

input
#!/bin/bash
set -e
OFFSET=$(grep -onam1 '^__DATA_...

correct output
50

user output
A
C
C
C
A
...
Truncated

Test 3

Group: 3

Verdict: ACCEPTED

input
#!/bin/bash
set -e
OFFSET=$(grep -onam1 '^__DATA_...

correct output
50

user output
C
A
C
C
A
...
Truncated