Submission #127800

#TimeUsernameProblemLanguageResultExecution timeMemory
127800mirbek01Paint By Numbers (IOI16_paint)C++11
59 / 100
3 ms632 KiB
#include "paint.h" #include <bits/stdc++.h> using namespace std; const int N = 2e5 + 3; int pref[3][N], dp[105][N], f[4][N], pos[N], n, m; string solve_puzzle(string s, vector<int> c) { n = (int)s.size(); m = (int)c.size(); s = ' ' + s; string ans; for(int i = 1; i <= n; i ++){ if(s[i] == '_') pref[1][i] ++; if(s[i] == 'X') pref[2][i] ++, pos[i] = i; pref[1][i] += pref[1][i - 1]; pref[2][i] += pref[2][i - 1]; pos[i] = max(pos[i], pos[i - 1]); } for(int i = c[0]; i <= n; i ++){ int wh = pref[1][i] - pref[1][i - c[0]]; if(!wh && !pref[2][i - c[0]]) dp[0][i] = 1; dp[0][i] += dp[0][i - 1]; } int sum = c[0] + 1; for(int i = 1; i < m; i ++){ for(int j = c[i] + sum; j <= n; j ++){ int can = dp[i - 1][j - c[i] - 1] - dp[i - 1][ pos[j - c[i] - 1] ]; if(can && (pref[1][j] - pref[1][j - c[i]]) == 0){ dp[i][j] = 1; } dp[i][j] += dp[i][j - 1]; } sum += c[i] + 1; } int pt = 1; for(int i = 0; i < m; i ++){ while(dp[i][pt] - dp[i][pt - 1] == 0) pt ++; f[0][pt - c[i] + 1] ++; f[0][pt + 1] --; } for(int i = 1; i <= n; i ++) f[0][i] += f[0][i - 1]; for(int i = 1; i <= n; i ++){ if(!f[0][i]) f[1][i] = 1; } int lst = n; for(int i = m - 1; i >= 0; i --){ bool ok = 1; int l; for(int j = lst; j >= 1; j --){ if(dp[i][j] - dp[i][j - 1]){ f[2][j - c[i] + 1] ++; f[2][j + 1] --; if(ok){ f[3][j - c[i] + 1] --; lst = j - c[i] - 1; ok = 0; } l = j - c[i] + 1; } } f[3][l] ++; } for(int i = 1; i <= n; i ++){ f[2][i] += f[2][i - 1]; f[3][i] += f[3][i - 1]; if(f[2][i]) f[0][i] = 1; if(f[3][i]) f[1][i] = 1; } for(int i = 1; i <= n; i ++){ if(f[0][i] && f[1][i]) ans += '?'; else if(f[0][i]) ans += 'X'; else ans += '_'; } return ans; }

Compilation message (stderr)

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:81:19: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
             f[3][l] ++;
             ~~~~~~^
#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...