Submission #1276610

#TimeUsernameProblemLanguageResultExecution timeMemory
1276610k12_khoiPaint By Numbers (IOI16_paint)C++17
32 / 100
67 ms444 KiB
#include "paint.h" #include <bits/stdc++.h> using namespace std; const int N=1e5+5; int n,k,x; int sz[N],pre[N],suf[N]; bool f[N],g[N]; string s; vector <int> c; string solve_puzzle(string s,vector <int> c) { string ans=s; int k=c.size(); int n=s.size(); string t=s; function <void(int)> ql = [&] (int i) -> void { if (i==n) { int cur=0; for (int i=0;i<n;i++) sz[i]=0; for (int i=0;i<n;i++) { if (t[i]=='_') { if (sz[cur]) cur++; } else sz[cur]++; } if (sz[cur]) cur++; if (cur==k) { for (int i=0;i<k;i++) if (c[i]!=sz[i]) return; for (int i=0;i<n;i++) if (t[i]=='X') f[i]=true; else g[i]=true; } return; } if (s[i]=='.') { t[i]='X'; ql(i+1); t[i]='_'; ql(i+1); } else ql(i+1); }; auto sub3 = [&] () { int sum=k-1; for (int i=0;i<k;i++) sum+=c[i]; if (sum==n) { int cur=0; for (int i=0;i<k;i++) { for (int j=cur;j<cur+c[i];j++) ans[j]='X'; if (i!=k-1) { ans[cur+c[i]]='_'; cur+=c[i]+1; } } } else { int cur=0; for (int i=0;i<k;i++) { pre[cur+c[i]]++; cur+=c[i]+1; } cur=n-1; for (int i=k-1;i>=0;i--) { suf[cur-c[i]]++; cur-=c[i]+1; } pre[0]=0; for (int i=1;i<n;i++) pre[i]+=pre[i-1]; suf[n-1]=0; for (int i=n-2;i>=0;i--) suf[i]+=suf[i+1]; for (int i=0;i<n;i++) if (pre[i]+suf[i]>=k) ans[i]='?'; else ans[i]='X'; } return ans; }; if (n>20) return sub3(); ql(0); for (int i=0;i<n;i++) if (ans[i]=='.') { if (f[i] and g[i]) ans[i]='?'; else if (f[i]) ans[i]='X'; else ans[i]='_'; } return ans; }

Compilation message (stderr)

paint.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
paint_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
#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...