Submission #598488

#TimeUsernameProblemLanguageResultExecution timeMemory
598488chirathnirodhaPaint By Numbers (IOI16_paint)C++17
0 / 100
0 ms212 KiB
#include "paint.h" #include<bits/stdc++.h> #include <cstdlib> using namespace std; #define PB push_back #define MP make_pair #define F first #define S second #define P push #define I insert string solve_puzzle(string s, vector<int> c) { int n=s.size(),k=c.size(); bool dp[n][k];memset(dp,false,sizeof(dp)); int lb[n],lw[n]; int cb=-1,cw=-1; for(int i=0;i<n;i++){ lb[i]=cb;lw[i]=cw; if(s[i]=='X')cb=i; if(s[i]=='_')cw=i; } vector<int> val[k]; for(int i=0;i<n;i++){ for(int j=0;j<k;j++){ if(s[i]=='_' || i-c[j]<-1)continue; if(i-c[j]==-1){ if(lw[i]<=i-c[j] && j==0){ dp[i][j]=true; val[j].PB(i); } continue; } if(lw[i]>i-c[j])continue; int lastbl=lb[i-c[j]+1]; if(j==0 && lastbl!=-1)continue; if(j>0){ auto low=lower_bound(val[j-1].begin(),val[j-1].end(),lastbl); if(low==val[j-1].end() || *low>=i-c[j])continue; } dp[i][j]=true; val[j].PB(i); } } queue<pair<int,int> > q; for(int i=0;i<val[k-1].size();i++){ if(val[k-1][i]>cb)break; q.P(MP(val[k-1][i],k-1)); } set<int> bl,wh; for(int i=0;i<n;i++){ if(s[i]=='.'){ bl.I(i); wh.I(i); } } bool canbl[n],canwh[n]; memset(canbl,false,sizeof(canbl));memset(canwh,false,sizeof(canwh)); while(!q.empty()){ pair<int,int> p=q.front();q.pop(); if(p.S==0)continue; int l=p.F-c[p.S]+1;int r=p.F; //Mark Black auto bx=lower_bound(bl.begin(),bl.end(),l); auto by=lower_bound(bl.begin(),bl.end(),r); auto x=bx; while(true){ if(x==bl.end())break; canbl[*x]=true; if(x==by)break; x++; } if(bx!=bl.end())bl.erase(bx,by); //Mark White auto wx=upper_bound(wh.begin(),wh.end(),lb[l]); auto wy=lower_bound(wh.begin(),wh.end(),l-1); auto y=wx; while(true){ if(y==wh.end())break; canwh[*y]=true; if(y==wy)break; y++; } if(wx!=wh.end())wh.erase(wx,wy); //Find next auto px=lower_bound(val[p.S-1].begin(),val[p.S-1].end(),lb[l]); auto py=lower_bound(val[p.S-1].begin(),val[p.S-1].end(),l-2); auto z=px; while(true){ if(z==val[p.S-1].end())break; q.P(MP(*z,p.S-1)); if(z==py)break; z++; } if(px!=val[p.S-1].end())val[p.S-1].erase(px,py); } for(int i=0;i<n;i++){ if(s[i]=='.'){ if(canbl[i] && canwh[i])s[i]='?'; else if(canbl[i])s[i]='X'; else s[i]='_'; } } return s; }

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i=0;i<val[k-1].size();i++){
      |                 ~^~~~~~~~~~~~~~~~
#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...