제출 #343767

#제출 시각아이디문제언어결과실행 시간메모리
343767bigDuckPaint By Numbers (IOI16_paint)C++14
100 / 100
711 ms239656 KiB
#include "paint.h" #include <cstdlib> #include<bits/stdc++.h> using namespace std; #define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define mp make_pair #define pb push_back #define ft first #define sc second #define ll long long #define pii pair<int, int> #define count_bits __builtin_popcount string res; int N, K; vector<int> C; string S; bool suf1[200010][101], pref1[200010][101];//negre (numai capete) bool suf2[200010][101], pref2[200010][101];//albe int sum[200010]; int sum2[200010][101], sum3[200010][101]; int get_sum(int l, int r){ return sum[r]-sum[l-1]; } //numarul punctelor din dreapta, care sunt capete drepte ale portiunii j, si portiunea neagra a j-a contine punctul r int get_sum2(int l, int j){ return sum2[min(l+C[j-1]-1, N) ][j]-sum2[l-1][j]; } //numarul punctelor din stanga, care sunt capete stangi ale portiunii K-j, si portiunea neagra a K-j-a contine punctul r int get_sum3(int r, int j){ return sum3[r][K-j+1]-sum3[max(r-C[j-1]+1-1, 1) ][K-j+1]; } void build(){ for(int i=1; i<=N; i++){ sum[i]=sum[i-1]; if(S[i-1]=='_'){ sum[i]++; } } pref2[0][0]=true; for(int i=1; i<=N; i++){ for(int j=0; j<=K; j++){ if( (j>0) && (i>=(C[j-1])) && ( get_sum(i-C[j-1]+1, i)==0 ) && ( pref2[i-C[j-1] ][j-1] ) ){ pref1[i][j]=true; } if( (S[i-1]!='X') && ( (pref2[i-1][j]==true) || (pref1[i-1][j]==true) ) ){ pref2[i][j]=true; } } } suf2[N+1][0]=true; for(int i=N; i>=1; i--){ for(int j=0; j<=K; j++){ if((j>0) && ( (i+C[K-j]-1)<=N ) && (get_sum(i, i+C[K-j]-1)==0 ) && (suf2[i+C[K-j] ][j-1]==true) ){ suf1[i][j]=true; } if( (S[i-1]!='X') && ( (suf1[i+1][j]==true) || (suf2[i+1][j]==true) ) ){ suf2[i][j]=true; } } } for(int i=1; i<=N; i++){ for(int j=0; j<=K;j++){ sum2[i][j]=sum2[i-1][j]; if( (pref1[i][j]==true) &&(suf2[i+1][K-j]==true) ){ sum2[i][j]++; } sum3[i][j]=sum3[i-1][j]; if( (suf1[i][j]==true) && (pref2[i-1][K-j]==true) ){ sum3[i][j]++; } } } } void build_res(){ res.resize(N); for(int i=0; i<N; i++){ res[i]='?'; } for(int i=1; i<=N; i++){ bool black=false; bool white=false; for(int j=0; j<=K; j++){ if( ( (j>0) && ( ( get_sum2(i, j)>0 ) ) ) || ( (j>0) && (get_sum3(i, j)) ) ){ black=true; } if( ( (pref2[i][j]==true) && ( (suf1[i+1][K-j]==true) || (suf2[i+1][K-j]==true) ) ) ){ white=true; } } if( (white) && (black) ){ res[i-1]='?'; } else{ if(white){ res[i-1]='_'; } else{ res[i-1]='X'; } } } } std::string solve_puzzle(std::string s, std::vector<int> c) { N=s.length(); K=c.size(); C=c; S=s; build(); build_res(); return res; }
#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...