Submission #571825

#TimeUsernameProblemLanguageResultExecution timeMemory
571825PiejanVDCPaint By Numbers (IOI16_paint)C++17
59 / 100
1 ms308 KiB
#include <bits/stdc++.h> //#include "paint.h" using namespace std; vector<int>v; vector<int>prefX, prefW; vector<int>le,ri; string s; int n,k; bool dfs(int i, int x) { if(i == k) { if(prefX[n] - prefX[min(n,x)] != 0) return 0; return 1; } if(x >= n || x + v[i] > n || (x != 0 && s[x-1] == 'X')) return 0; bool ok = 0; if(prefW[x+v[i]] == prefW[x] && (x + v[i] == n || s[x+v[i]] != 'X')) { ok = dfs(i+1, x + v[i] + 1 ); } if(ok) { le[i] = x; return 1; } return dfs(i, x+1); } bool rdfs(int i, int x) { if(i == -1) { if(prefX[max(0,x+1)] != 0) return 0; return 1; } //cout << i << " " << x << '\n'; if(x < 0 || x - v[i] < -1 || s[x+1] == 'X') return 0; bool ok = 0; if(prefW[x+1] == prefW[x - v[i] + 1] && (x - v[i] == -1 || s[x - v[i]] != 'X')) { ok = rdfs(i-1, x - v[i] - 1); } if(ok) { ri[i] = x - v[i] + 1; return 1; } return rdfs(i, x-1); } string solve_puzzle(string S, vector<int> c) { v = c; s = S; n = (int)s.length(); k = (int)c.size(); prefW.resize(n+5,0); prefX.resize(n+5,0); le.resize(n+5,0); ri.resize(n+5,-1); prefX[0] = prefW[0] = 0; s += '.'; for(int i = 0 ; i < n ; i++) { prefX[i+1] = prefX[i] + (s[i] == 'X' ? 1 : 0); prefW[i+1] = prefW[i] + (s[i] == '_' ? 1 : 0); } dfs(0, 0); rdfs(k-1, n-1); for(int i = 0 ; i < k ; i++) { if(ri[i] == -1) { assert(0); } } string ans = ""; for(int i = 0 ; i < n ; i++) { ans += '_'; //cout << prefX[i+1] << ' ' << le[i] << ' ' << ri[i] << '\n'; } for(int i = 0 ; i < k ; i++) { if(le[i] + v[i] - 1 >= ri[i]) { for(int ii = ri[i] ; ii <= le[i] + v[i] - 1 ; ii++) { ans[ii] = 'X'; } } //cout << i << " " << ans << '\n'; for(int ii = ri[i] ; ii < ri[i] + v[i] ; ii++) { if(s[ii] != 'X' && ans[ii] != 'X') { ans[ii] = '?'; } } for(int ii = le[i] ; ii <= ri[i] ; ii++) { if(prefW[ii + v[i]] == prefW[ii] && (ii + v[i] == n || v[ii + v[i]] != 'X') && (ii-1 == -1 || v[ii-1] != 'X')) { for(int j = ii ; j < ii + v[i] ; j++) { if(s[j] != 'X' && ans[j] != 'X') ans[j] = '?'; } } } } for(int i = 0 ; i < n ; i++) { if(s[i] == 'X') ans[i] = 'X'; } return ans; } #include <vector> #include <string> #include <cstdio> #include <cassert>
#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...