oj.uz

Submission #738830

# Submission time Handle Problem Language Result Execution time Memory
738830 2023-05-09T14:18:16 Z flappybird Present (RMI21_present) C++17
100 / 100
 1726 ms 9656 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1711 ms 9548 KB Output is correct
2 Correct 1677 ms 9544 KB Output is correct
3 Correct 1669 ms 9544 KB Output is correct
4 Correct 1624 ms 9608 KB Output is correct
5 Correct 1725 ms 9544 KB Output is correct
6 Correct 1669 ms 9572 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1711 ms 9548 KB Output is correct
2 Correct 1677 ms 9544 KB Output is correct
3 Correct 1669 ms 9544 KB Output is correct
4 Correct 1624 ms 9608 KB Output is correct
5 Correct 1725 ms 9544 KB Output is correct
6 Correct 1669 ms 9572 KB Output is correct
7 Correct 1593 ms 9612 KB Output is correct
8 Correct 1635 ms 9548 KB Output is correct
9 Correct 1660 ms 9588 KB Output is correct
10 Correct 1704 ms 9544 KB Output is correct
11 Correct 1658 ms 9548 KB Output is correct
12 Correct 1643 ms 9560 KB Output is correct

Subtask #3
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1711 ms 9548 KB Output is correct
2 Correct 1677 ms 9544 KB Output is correct
3 Correct 1669 ms 9544 KB Output is correct
4 Correct 1624 ms 9608 KB Output is correct
5 Correct 1725 ms 9544 KB Output is correct
6 Correct 1669 ms 9572 KB Output is correct
7 Correct 1593 ms 9612 KB Output is correct
8 Correct 1635 ms 9548 KB Output is correct
9 Correct 1660 ms 9588 KB Output is correct
10 Correct 1704 ms 9544 KB Output is correct
11 Correct 1658 ms 9548 KB Output is correct
12 Correct 1643 ms 9560 KB Output is correct
13 Correct 1656 ms 9552 KB Output is correct
14 Correct 1622 ms 9656 KB Output is correct
15 Correct 1720 ms 9548 KB Output is correct
16 Correct 1625 ms 9580 KB Output is correct
17 Correct 1698 ms 9544 KB Output is correct
18 Correct 1609 ms 9548 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1711 ms 9548 KB Output is correct
2 Correct 1677 ms 9544 KB Output is correct
3 Correct 1669 ms 9544 KB Output is correct
4 Correct 1624 ms 9608 KB Output is correct
5 Correct 1725 ms 9544 KB Output is correct
6 Correct 1669 ms 9572 KB Output is correct
7 Correct 1593 ms 9612 KB Output is correct
8 Correct 1635 ms 9548 KB Output is correct
9 Correct 1660 ms 9588 KB Output is correct
10 Correct 1704 ms 9544 KB Output is correct
11 Correct 1658 ms 9548 KB Output is correct
12 Correct 1643 ms 9560 KB Output is correct
13 Correct 1656 ms 9552 KB Output is correct
14 Correct 1622 ms 9656 KB Output is correct
15 Correct 1720 ms 9548 KB Output is correct
16 Correct 1625 ms 9580 KB Output is correct
17 Correct 1698 ms 9544 KB Output is correct
18 Correct 1609 ms 9548 KB Output is correct
19 Correct 1648 ms 9544 KB Output is correct
20 Correct 1631 ms 9544 KB Output is correct
21 Correct 1628 ms 9548 KB Output is correct
22 Correct 1542 ms 9556 KB Output is correct
23 Correct 1614 ms 9548 KB Output is correct
24 Correct 1610 ms 9512 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1711 ms 9548 KB Output is correct
2 Correct 1677 ms 9544 KB Output is correct
3 Correct 1669 ms 9544 KB Output is correct
4 Correct 1624 ms 9608 KB Output is correct
5 Correct 1725 ms 9544 KB Output is correct
6 Correct 1669 ms 9572 KB Output is correct
7 Correct 1593 ms 9612 KB Output is correct
8 Correct 1635 ms 9548 KB Output is correct
9 Correct 1660 ms 9588 KB Output is correct
10 Correct 1704 ms 9544 KB Output is correct
11 Correct 1658 ms 9548 KB Output is correct
12 Correct 1643 ms 9560 KB Output is correct
13 Correct 1656 ms 9552 KB Output is correct
14 Correct 1622 ms 9656 KB Output is correct
15 Correct 1720 ms 9548 KB Output is correct
16 Correct 1625 ms 9580 KB Output is correct
17 Correct 1698 ms 9544 KB Output is correct
18 Correct 1609 ms 9548 KB Output is correct
19 Correct 1648 ms 9544 KB Output is correct
20 Correct 1631 ms 9544 KB Output is correct
21 Correct 1628 ms 9548 KB Output is correct
22 Correct 1542 ms 9556 KB Output is correct
23 Correct 1614 ms 9548 KB Output is correct
24 Correct 1610 ms 9512 KB Output is correct
25 Correct 1652 ms 9548 KB Output is correct
26 Correct 1679 ms 9548 KB Output is correct
27 Correct 1726 ms 9544 KB Output is correct
28 Correct 1676 ms 9544 KB Output is correct
29 Correct 1638 ms 9548 KB Output is correct
30 Correct 1598 ms 9552 KB Output is correct