제출 #388900

#제출 시각아이디문제언어결과실행 시간메모리
388900aarrPaint By Numbers (IOI16_paint)C++14
100 / 100
415 ms126404 KiB
#include "paint.h" #include <cstdlib> #include <bits/stdc++.h> using namespace std; const int N = 200 * 1000 + 5, K = 105; bool dp[N][K][3]; //vector <pair <int, pair <int, int> > > adj[N][K][3]; bool mark[N][K][3]; int e[N]; bool ans1[N]; int lt[N]; /*void dfs(int x, int y, int z) { if (mark[x][y][z]) { return; } mark[x][y][z] = true; for (auto p : adj[x][y][z]) { dfs(p.first, p.second.first, p.second.second); } }*/ std::string solve_puzzle(std::string s, std::vector<int> c) { string ans = ""; int n = s.size(), k = c.size(); dp[0][0][0] = true; lt[0] = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j <= k; j++) { if (s[i - 1] != 'X') { if (dp[i - 1][j][0]) { dp[i][j][0] = true; // adj[i][j][0].push_back({i - 1, {j, 0}}); } if (dp[i - 1][j][1]) { dp[i][j][0] = true; // adj[i][j][0].push_back({i - 1, {j, 1}}); } } if (j && s[i - 1] != '_') { int x = c[j - 1]; if (dp[i - x][j - 1][0] && lt[i - 1] <= i - x) { dp[i][j][1] = true; // adj[i][j][1].push_back({i - x, {j - 1, 0}}); } } lt[i] = lt[i - 1]; if (s[i - 1] == '_') { lt[i] = i; } } } if (dp[n][k][0]) { mark[n][k][0] = true; } if (dp[n][k][1]) { mark[n][k][1] = true; } for (int i = n; i; i--) { for (int j = 0; j <= k; j++) { if (mark[i][j][0]) { if (dp[i - 1][j][0]) { mark[i - 1][j][0] = true; // adj[i][j][0].push_back({i - 1, {j, 0}}); } if (dp[i - 1][j][1]) { mark[i - 1][j][1] = true; // adj[i][j][0].push_back({i - 1, {j, 1}}); } } if (mark[i][j][1]) { int x = c[j - 1]; if (dp[i - x][j - 1][0] && lt[i - 1] <= i - x) { mark[i - x][j - 1][0] = true; // adj[i][j][1].push_back({i - x, {j - 1, 0}}); } } } } int cnt = 0; for (int i = n; i > 0; i--) { cnt -= e[i]; for (int j = 1; j <= k; j++) { if (mark[i][j][1]) { cnt++; e[i - c[j - 1]]++; } } // cout << "72 " << i << " " << cnt << endl; if (cnt > 0) { ans1[i] = true; } } for (int i = 1; i <= n; i++) { bool b = false; for (int j = 0; j <= k; j++) { if (mark[i][j][0]) { b = true; } } if (b) { if (ans1[i]) { ans += '?'; } else { ans += '_'; } } else { ans += 'X'; } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...