Submission #129466

#	Time	Username	Problem	Language	Result	Execution time	Memory
129466		E869120	Binary Subsequences (info1cup17_binary)	C++14	43 / 100	1088 ms	1036 KiB

binary

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

int dp[30], t[30][2];

long long solve(int n, int mask) {
	for (int i = 0; i <= n; i++) { t[i][0] = n; t[i][1] = n; dp[i] = 0; }
	for (int i = 0; i < n; i++) {
		if ((mask & (1 << i)) == 0) t[i][0] = i;
		else t[i][1] = i;
	}
	for (int i = n - 1; i >= 0; i--) { for (int j = 0; j < 2; j++) t[i][j] = min(t[i][j], t[i + 1][j]); }

	dp[0] = 1;
	for (int i = 0; i < n; i++) {
		dp[t[i][0] + 1] += dp[i];
		dp[t[i][1] + 1] += dp[i];
	}
	int sum = 0;
	for (int i = 1; i <= n; i++) sum += dp[i];
	return sum;
}

int len[1 << 20], num[1 << 20];

void search() {
	for (int i = 1; i <= 100000; i++) len[i] = 0;
	for (int i = 1; i <= 21; i++) {
		for (int j = 0; j < (1 << (i - 1)); j++) {
			int G = solve(i, j);
			if (len[G] == 0) { len[G] = i; num[G] = j; }
		}
	}
}

int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}

int euler(int pos) {
	int cnt = 0;
	for (int i = 1; i <= pos; i++) {
		if (gcd(i, pos) == 1) cnt++;
	}
	return cnt;
}

int main() {
	search();
	int T; cin >> T;
	for (int i = 1; i <= T; i++) {
		int A; cin >> A;
		cout << euler(A + 2) << endl;
		for (int j = 0; j < len[A]; j++) { if (j) cout << " "; cout << (num[A] / (1 << j)) % 2; } cout << endl;
	}
	return 0;
}

• Subtask 1: 43 / 43
• Subtask 2: 0 / 39
• Subtask 3: 0 / 18