제출 #598656

#제출 시각아이디문제언어결과실행 시간메모리
598656chirathnirodhaPaint By Numbers (IOI16_paint)C++17
80 / 100
2079 ms1572 KiB
#include "paint.h" #include<bits/stdc++.h> 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); } } set<int> bl,wh; bool visited[n][k];memset(visited,false,sizeof(visited)); bool canbl[n],canwh[n]; memset(canbl,false,sizeof(canbl));memset(canwh,false,sizeof(canwh)); for(int i=0;i<n;i++){ if(s[i]=='.'){ bl.I(i); wh.I(i); } } queue<pair<int,int> > q; for(int i=0;i<val[k-1].size();i++){ if(val[k-1][i]>=cb)q.P(MP(val[k-1][i],k-1)); } if(!q.empty())for(int i=q.front().F+1;i<n;i++)canwh[i]=true; while(!q.empty()){ pair<int,int> p=q.front();q.pop(); 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+1); if(by==bl.begin())bx=bl.end(); else{ by--; if(*by<*bx)bx=bl.end(); } auto x=bx; while(true){ if(x==bl.end())break; canbl[*x]=true; if(x==by)break; x++; } if(by!=bl.end())by++; if(bx!=bl.end())bl.erase(bx,by); if(p.S==0){ if(wh.empty())continue; auto itr=wh.begin(); for(itr;itr!=wh.end();itr++){ if(*itr>=l)break; canwh[*itr]=true; } wh.erase(wh.begin(),itr); continue; } //Mark White auto px=lower_bound(val[p.S-1].begin(),val[p.S-1].end(),lb[l]); auto wx=upper_bound(wh.begin(),wh.end(),max(lb[l],*px)); auto wy=lower_bound(wh.begin(),wh.end(),l); if(wy==wh.begin())wx=wh.end(); else{ wy--; if(*wy<*wx)wx=wh.end(); } auto y=wx; while(true){ if(y==wh.end())break; canwh[*y]=true; if(y==wy)break; y++; } if(wy!=wh.end())wy++; if(wx!=wh.end())wh.erase(wx,wy); //Find next auto py=lower_bound(val[p.S-1].begin(),val[p.S-1].end(),l-1); if(py==val[p.S-1].begin())px=val[p.S-1].end(); else{ py--; if(*py<*px)px=val[p.S-1].end(); } auto z=px; while(true){ if(z==val[p.S-1].end())break; if(visited[*z][p.S-1]==false){ q.P(MP(*z,p.S-1)); visited[*z][p.S-1]=true; } if(z==py)break; z++; } } 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; }

컴파일 시 표준 에러 (stderr) 메시지

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:56:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(int i=0;i<val[k-1].size();i++){
      |                 ~^~~~~~~~~~~~~~~~
paint.cpp:85:17: warning: statement has no effect [-Wunused-value]
   85 |             for(itr;itr!=wh.end();itr++){
      |                 ^~~
#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...