Submission #1148583

#TimeUsernameProblemLanguageResultExecution timeMemory
1148583weakweakweakBinary Subsequences (info1cup17_binary)C++20
43 / 100
57 ms61764 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("Ofast") using pii = pair<int,int>; #define fs first #define sc second int cnt[2010] = {0}; int dp[2010][2010]; // dp[目前dp值][上一個0] = 上一個1 pii lst[2010][2010]; int len[2010][2010] = {0}; char cc[2010][2010]; string s[2010]; queue<int> q[2010]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); for (int i = 0; i <= 2005; i++) for (int j = 0; j <= 2005; j++) dp[i][j] = 888888, len[i][j] = 114514; dp[1][0] = 0; len[1][0] = 0; q[1].push(0); for (int i = 1; i <= 2005; i++) { while (q[i].size()) { int lst0 = q[i].front(); q[i].pop(); int lst1 = dp[i][lst0]; { // 接 0 int ni = i*2 - lst0; if (ni <= 2005) { cnt[ni]++; int n0 = i, n1 = lst1; q[ni].push(n0); cc[ni][n0] = '0'; dp[ni][n0] = n1; lst[ni][n0] = make_pair(i,lst0); len[ni][n0] = len[i][lst0] + 1; } } { // 接 0 int ni = i*2 - lst1; if (ni <= 2005) { cnt[ni]++; int n0 = lst0, n1 = i; q[ni].push(n0); cc[ni][n0] = '1'; dp[ni][n0] = n1; lst[ni][n0] = make_pair(i,lst0); len[ni][n0] = len[i][lst0] + 1; } } } } int t; cin >> t; while (t--) { int k; cin >> k; k++; cout << cnt[k] << '\n'; int ansid = 0; for (int i = 0; i <= 2005; i++) if (len[k][i] < len[k][ansid]) ansid = i; vector<char> ans; pii me = {k, ansid}; while (me != make_pair(1,0)) { ans.push_back(cc[me.fs][me.sc]); me = lst[me.fs][me.sc]; } reverse(ans.begin(), ans.end()); for (char c : ans) cout << c << ' '; cout << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...