| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1137759 | ackhava | Paint By Numbers (IOI16_paint) | C++20 | 0 ms | 0 KiB |
#include "paint.h"
#include <bits/stdc++.h>
#include <cstdlib>
#define REP(v, i, j) for (int v = i; v != j; v++)
#define FORI(v) for (auto i : v)
#define FORJ(v) for (auto j : v)
#define OUT(v, a) \
FORI(v) \
cout << i << a;
#define OUTS(v, a, b) \
cout << v.size() << a; \
OUT(v, b)
#define in(a, n) \
REP(i, 0, n) \
cin >> a[i];
#define SORT(v) sort(begin(v), end(v))
#define REV(v) reverse(begin(v), end(v))
#define MEMSET(m) memset(m, -1, sizeof m)
#define pb push_back
#define fi first
#define se second
#define detachIO \
ios_base::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
using namespace std;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<pii, pii> piiii;
// string merge(string a, string b){
// if(a[0]=='-')return b;
// if(b[0]=='-')return a;
// REP(i,0,b.size()){
// if(a[i]==b[i])continue;
// if(a[i]!=b[i])a[i]='?';
// }
// return a;
// }
// bool fits(string s, int len, bool last){
// REP(i,0,len){
// if(!s.size())return false;
// if(s.back()=='_')return false;
// s.pop_back();
// }
// if(last)return true;
// if(!s.size())return false;
// if(s.back()=='#')return false;
// return true;
// }
// string move_str(string s, vector<int> c, int special){
// cerr<<s<<" / "<<c.size()<<" / "<<special<<endl;
// if(!c.size()){
// for(auto &i:s)i='_';
// return s;
// }
// if(!s.size())return "-";
// cerr<<"> "<<s<<" / "<<c.size()<<" / "<<special<<endl;
// if(c.size()==(special+1)){
// char ch=s.back();
// s.pop_back();
// string str=move_str(s,c,special)+ch;
// s.pb(ch);
// if(fits(s,c.back(),c.size()==1)){
// string t="";
// REP(i,0,c.back())t.pb('#'),s.pop_back();
// if(c.size()!=1)t.pb('_'),s.pop_back();
// REV(t);
// c.pop_back();
// str=merge(str,move_str(s,c,special)+t);
// }
// } else {
// if(fits(s,c.back(),c.size()==1)){
// string t="";
// REP(i,0,c.back())t.pb('#'),s.pop_back();
// if(c.size()!=1)t.pb('_'),s.pop_back();
// REV(t);
// c.pop_back();
// return move_str(s,c,special)+t;
// } else {
// char ch=s.back();
// s.pop_back();
// return move_str(s,c,special)+ch;
// }
// }
// }
string s;
vector<int> c;
short prv[200000];
short mem1[200000][400];
short mem2[200000][400];
short d1(int n, int k){
if(n<=-1 && k!=-1)return 0;
if(n<=-1)return 1;
short &ans=mem1[n+2][k+2];
if(ans!=-1)return ans;
if(k==-1 && s[n]=='X')return ans=0;
if(k==-1)return ans=d1(n-1,k);
ans=d1(n-1,k);
if(s[n]=='X')ans=0;
if(d1(n-c[k]-1,k-1) && prv[n]>=c[k])ans=1;
return ans;
}
short d2(int n, int k){
if(n>=s.size() && k!=c.size())return 0;
if(n>=s.size())return 1;
short &ans=mem2[n+2][k+2];
if(ans!=-1)return ans;
if(k==c.size() && s[n]=='X')return ans=0;
if(k==c.size())return ans=d2(n+1,k);
ans=d2(n+1,k);
if(s[n]=='X')ans=0;
if((n+c[k]-1)<s.size() && d2(n+c[k]+1,k+1) && prv[n+c[k]-1]>=c[k])ans=1;
return ans;
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
string ans="";
::s=s;
::c=c;
prv[0]=1;
if(s[0]=='_')prv[0]=0;
REP(i,1,s.size()){
prv[i]=prv[i-1]+1;
if(s[i]=='_')prv[i]=0;
}
MEMSET(mem1);
MEMSET(mem2);
REP(i,0,s.size())ans.pb('.');
REP(k,0,c.size()){
string prx="";
REP(i,0,s.size())prx.pb('.');
REP(i,0,s.size()){
if((i+c[k]-1)>=s.size())break;
if(prv[i+c[k]-1]<c[k])continue;
if(!d1(i-2,k-1))continue;
if(i && s[i-1]=='X')continue;
if((i+c[k])<s.size() && s[i+c[k]]=='X')continue;
if(!d2(i+c[k]+1,k+1))continue;
REP(j,i,i+c[k]){if(s[j]=='_')goto nxt;}
REP(j,i,i+c[k])ans[j]='X';
prx[i]='>';
nxt:
}
// cout<<"> "<<prx<<endl;
}
REP(i,0,s.size()){
bool p=false;
REP(k,0,c.size()+1){
if(!d1(i-1,k-1))continue;
if(!d2(i+1,k))continue;
p=true;
break;
}
if(!p)continue;
if(s[i]=='X')continue;
if(ans[i]=='X')ans[i]='?';
else ans[i]='_';
}
return ans;
}