Submission #479669

#TimeUsernameProblemLanguageResultExecution timeMemory
479669julian33Paint By Numbers (IOI16_paint)C++14
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #define deb(...) logger(#__VA_ARGS__, __VA_ARGS__) template<typename ...Args> void logger(string vars, Args&&... values) { cerr<<vars<<" = "; string delim=""; (...,(cerr<<delim<<values,delim=", ")); cerr<<"\n"; } #else #define deb(...) logger(#__VA_ARGS__, __VA_ARGS__) template<typename ...Args> void logger(string vars, Args&&... values) {} #endif #define pb push_back #define sz(x) (int)(x.size()) typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; template<typename T> inline void maxa(T& a,T b){a=max(a,b);} template<typename T> inline void mina(T& a,T b){a=min(a,b);} mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int mxN=2e5+5; //make sure this is right const int mod=1e9+7; int good[mxN][105],good2[mxN][105]; int main(){ cin.sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifdef LOCAL freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif string s; cin>>s; int n=sz(s); deb(n); int k; cin>>k; vector<int> c(k); for(int &i:c) cin>>i; vector<int> psa(n+1); for(int i=1;i<=n;i++) psa[i]=psa[i-1]+(s[i-1]=='_'); queue<int> spots[k+2],pot[k+2]; spots[0].push(-1); for(int i=1;i<=n;i++){ for(int j=1;j<=k;j++){ if(i-c[j-1]-1>=0 && s[i-c[j-1]-1]=='X'){ while(sz(spots[j-1]) && spots[j-1].front()<i-c[j-1]) spots[j-1].pop(); while(sz(pot[j-1]) && pot[j-1].front()<i-c[j-1]) pot[j-1].pop(); } if(c[j-1]>i) continue; if(i-c[j-1]-1>=0 && s[i-c[j-1]-1]=='X') continue; if(psa[i]-psa[i-c[j-1]]>0) continue; while(sz(pot[j-1]) && pot[j-1].front()<i-c[j-1]){ spots[j-1].push(pot[j-1].front()); pot[j-1].pop(); } if(!sz(spots[j-1])) continue; if(i<n && s[i]=='X') continue; deb(i,j); good[i][j]=1; pot[j].push(i); } } for(int i=0;i<=k;i++){ while(sz(spots[i])) spots[i].pop(); while(sz(pot[i])) pot[i].pop(); } spots[k+1].push(n+2); for(int i=n;i>=1;i--){ for(int j=1;j<=k;j++){ if(i+c[j-1]-1<n && s[i+c[j-1]-1]=='X'){ while(sz(spots[j+1]) && spots[j+1].front()>i+c[j-1]) spots[j+1].pop(); while(sz(pot[j+1]) && pot[j+1].front()>i+c[j-1]) pot[j+1].pop(); } if(i+c[j-1]-1>n) continue; if(i+c[j-1]<=n && s[i+c[j-1]-1]=='X') continue; if(psa[i+c[j-1]-1]-psa[i-1]>0) continue; while(sz(pot[j+1]) && pot[j+1].front()>i+c[j-1]){ spots[j+1].push(pot[j+1].front()); pot[j+1].pop(); } if(!sz(spots[j+1])) continue; if(i>=2 && s[i-2]=='X') continue; deb(i,j); good2[i][j]=1; pot[j].push(i); } } vector<int> all(n+2); for(int i=1;i<=k;i++){ vector<int> sum(n+2); int cnt=0; for(int j=c[i-1];j<=n;j++){ if(good[j][i] && good2[j-c[i-1]+1][i]){ cnt++; sum[j-c[i-1]+1]++; sum[j+1]--; all[j-c[i-1]+1]++; all[j+1]--; } } for(int j=1;j<=n;j++){ sum[j]+=sum[j-1]; if(sum[j]==cnt) { s[j-1]='X'; } } } for(int i=1;i<=n;i++){ all[i]+=all[i-1]; if(all[i]==0){assert(s[i-1]!='X'),s[i-1]='_';} if(s[i-1]=='.') s[i-1]='?'; } cout<<s<<"\n"; }

Compilation message (stderr)

/usr/bin/ld: /tmp/cc43oAxs.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc9oWm7s.o:paint.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc43oAxs.o: in function `main':
grader.cpp:(.text.startup+0x213): undefined reference to `solve_puzzle(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status