This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |