Submission #738830

#	Time	Username	Problem	Language	Result	Execution time	Memory
738830		flappybird	Present (RMI21_present)	C++17	100 / 100	1726 ms	9656 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 201010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define X 19
bool chk1[1 << X];
bool chk2[1 << X];
int cnt[1 << X]; // available even set
ll sum[1 << X]; // sos dp of cnt
int mask[1 << X];
int gcda[50][50];
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int T;
	cin >> T;
	int i, j, k;
	for (i = 1; i < 50; i++) for (j = 1; j < 50; j++) gcda[i][j] = gcd(i, j);
	for (i = 0; i < (1 << X); i++) { // odd
		chk1[i] = true;
		for (j = 0; j < X; j++) if (i >> j & 1) {
			for (k = j + 1; k < X; k++) if (i >> k & 1) {
				int g = gcda[2 * j + 1][2 * k + 1] - 1 >> 1;
				if (!(i >> g & 1)) {
					chk1[i] = false;
					break;
				}
			}
			if (!chk1[i]) break;
		}
		if (chk1[i]) {
			mask[i] = 1 << X;
			mask[i]--;
			for (k = 0; k < X; k++) {
				for (j = 0; j < X; j++) if (i >> j & 1) {
					int g = gcda[2 * j + 1][2 * k + 2] - 1 >> 1;
					if (!(i >> g & 1)) {
						mask[i] ^= (1 << k);
						break;
					}
				}
			}
		}
	}
	for (i = 0; i < (1 << X); i++) { // even
		chk2[i] = true;
		int j, k;
		for (j = 0; j < X; j++) if (i >> j & 1) {
			for (k = j + 1; k < X; k++) if (i >> k & 1) {
				int g = gcda[2 * j + 2][2 * k + 2] - 1 >> 1;
				if (!(i >> g & 1)) {
					chk2[i] = false;
					break;
				}
			}
			if (!chk2[i]) break;
		}
	}
	while (T--) {
		//memset(isin, 0, sizeof(isin));
		ll K;
		cin >> K;
		int i, j, k;
		vector<int> ans;
		int oddmask = 0; // selected odd numbers
		int beven = 0; // banned even numbers
		int seven = 0; // selected even numbers
		int sodd = 0; // selected odd numbers
		for (i = 2 * X; i >= 1; i--) {
			//if (isin[i]) continue;
			int ind = i - 1 >> 1;
			if (!(i & 1)) beven |= (1 << ind);
			for (j = 0; j < (1 << X); j++) {
				if (chk2[j]) cnt[j] = 1;
				if (j & beven) cnt[j] = 0;
				if ((j & seven) != seven) cnt[j] = 0;
			}
			for (j = 0; j < (1 << X); j++) sum[j] = cnt[j];
			for (k = 0; k < X; k++) for (j = 0; j < (1 << X); j++) if (j & (1 << k)) sum[j] += sum[j ^ (1 << k)]; // sos dp
			ll all = 0;
			int i2 = ind;
			if (!(i & 1)) i2++;
			for (j = 0; j < 1 << i2; j++) if (chk1[sodd | j]) all += sum[mask[sodd | j]];
			if (all <= K) {
				ans.push_back(i);
				if (i & 1) sodd |= (1 << ind);
				else beven ^= (1 << ind), seven |= (1 << ind);
				K -= all;
			}
		}
		reverse(ans.begin(), ans.end());
		cout << ans.size() << bb;
		for (auto v : ans) cout << v << bb;
		cout << ln;
	}
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:33:40: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   33 |     int g = gcda[2 * j + 1][2 * k + 1] - 1 >> 1;
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
Main.cpp:46:41: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   46 |      int g = gcda[2 * j + 1][2 * k + 2] - 1 >> 1;
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
Main.cpp:60:40: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   60 |     int g = gcda[2 * j + 2][2 * k + 2] - 1 >> 1;
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
Main.cpp:81:16: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   81 |    int ind = i - 1 >> 1;
      |              ~~^~~
Main.cpp:75:7: warning: unused variable 'oddmask' [-Wunused-variable]
   75 |   int oddmask = 0; // selected odd numbers
      |       ^~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 21 / 21
• Subtask 3: 41 / 41
• Subtask 4: 14 / 14
• Subtask 5: 16 / 16