Submission #210108

#TimeUsernameProblemLanguageResultExecution timeMemory
210108NucleistPaint By Numbers (IOI16_paint)C++14
100 / 100
1024 ms178756 KiB
#include <bits/stdc++.h> #include "paint.h" using namespace std; #pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #define flash ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0) #define debug(x) cerr << " - " << #x << ": " << x << endl; #define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl; #define all(x) (x).begin(),(x).end() #define sz(x) (ll)x.size() #define ll long long #define INF 1000000000 #define MOD 1000000007 #define pb push_back #define ve vector<ll> #define dos pair<ll,ll> #define vedos vector<dos> #define rand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) struct greateri { template<class T> bool operator()(T const &a, T const &b) const { return a > b; } }; int n; vector<int>cal; string no; set<int>pos; int dp[200101][2][101]; int ans1[200101]; pair<int,int>ans2[200101]; int BIT[200101]; int update(int index,int val) { for (index++; index < n+1; index+=(index & (-index))) { BIT[index]+=val; } } int query(int index) { int val=0; for (index++; index > 0; index-=(index & (-index))) { val+=BIT[index]; } return val; } int update1(int l,int r,int val) { update(l,val); update(r+1,-val); } int solve(int index,int state,int gr) { if(index==n) { if(gr==cal.size())return 1; else return 0; } if(dp[index][state][gr]!=-1)return dp[index][state][gr]; int ans=0; if(no[index]=='_' || no[index]=='.') { ans=max(ans,solve(index+1,0,gr)); } if(ans==1) { ans1[index]=1; } int ans3=0; if(no[index]=='X' || (no[index]=='.' && state==0)) { auto u=pos.lower_bound(index); int next=index+cal[gr]-1; if(((*u)>next || u==pos.end()) && no[next+1]!='X' && next+1<=n && gr<=cal.size()) { ans3=max(ans3,solve(next+1,1,gr+1)); } } if(ans3==1) { ans2[index]={1,max(ans2[index].second,index+cal[gr]-1)}; } return dp[index][state][gr]=max(ans,ans3); } string solve_puzzle(string s,vector<int>c) { n=s.size(); cal=c; no=s; memset(dp,-1,sizeof dp); for (int i = 0; i < s.size(); ++i) { if(s[i]=='_')pos.insert(i); } solve(0,0,0); //debug(1); string fin; for (int i = 0; i < s.size(); ++i) { if(ans2[i].first==1) { update1(i,ans2[i].second,1); } } for (int i = 0; i < s.size(); ++i) { if(s[i]=='X')fin+='X'; else if(s[i]=='_')fin+='_'; else { int q = query(i); if(ans1[i]==1 && q==0)fin+='_'; else if(ans1[i]==0 && q>=1)fin+='X'; else fin+='?'; } } return fin; } //code the AC sol ! // BS/queue/map

Compilation message (stderr)

paint.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
paint.cpp:6:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
paint.cpp: In function 'int update(int, int)':
paint.cpp:39:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
paint.cpp: In function 'int update1(int, int, int)':
paint.cpp:53:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
paint.cpp: In function 'int solve(int, int, int)':
paint.cpp:58:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(gr==cal.size())return 1;
      ~~^~~~~~~~~~~~
paint.cpp:76:71: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(((*u)>next || u==pos.end()) && no[next+1]!='X' && next+1<=n && gr<=cal.size())
                                                                     ~~^~~~~~~~~~~~
paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:93:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < s.size(); ++i)
                  ~~^~~~~~~~~~
paint.cpp:100:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < s.size(); ++i)
                  ~~^~~~~~~~~~
paint.cpp:107:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < s.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...