| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 831045 | grogu | Ancient Machine 2 (JOI23_ancient2) | C++17 | 106 ms | 788 KiB |
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 "ancient2.h"
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define ld double
#define ll int
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define eb emplace_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}
#define si(a) (ll)(a.size())
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l,ll r){
return uniform_int_distribution<ll>(l,r)(rng);
}
#define mod 1000000007
ll add(ll x,ll y){
x+=y;
if(x<0){
x%=mod;
x+=mod;
}else{
if(x>=mod) x%=mod;
}
return x;
}
ll mul(ll a,ll b){
long long ans = (((long long)a)*((long long)b))%mod;
if(ans<0) ans+=mod;
return ans;
}
ll po(ll x,ll y){
if(y==0) return 1LL;
ll ans = po(x,y/2);
ans = mul(ans,ans);
if(y&1) ans = mul(ans,x);
return ans;
}
ll inv(ll x){return po(x,mod-2);}
#define maxn 1005
ll n;
ll a[maxn];
ll dp[maxn];
pll opt[maxn];
ll p;
ll hsh[maxn];
ll powe[maxn];
ll get(ll l,ll r){
return add(hsh[r],-mul(powe[r-l+1],hsh[l-1]));
}
ll ls[maxn],rs[maxn];
ll tsz = 0;
string Solve(int N) {
powe[0] = 1;
p = rnd(2,mod-1);
for(ll i = 1;i<maxn;i++) powe[i] = mul(powe[i-1],p);
n = N;
dp[0] = 0;
opt[0] = {-1,-1};
for(ll i = 0;i<n;i++){
//ceri(a,0,i-1);
//here;
//dbg(i);
if(i==0){
vector<ll> b = {1,1,2};
vector<ll> c = {2,1,2};
ll x = Query(3,b,c);
if(x==1) a[i] = 0;
else a[i] = 1;
}else{
ll m = i-1;
ll tsz = 0;
ll last = 3;
ls[last] = 1;
rs[last] = 2;
ls[2] = rs[2] = 2;
ls[1] = rs[1] = 1;
tsz = 3;
//dbg(i);
//dbg(m);
while(m!=-1){
pll p = opt[m];
//cerr<<m<< " "<<p.fi<< " "<<p.sc<<" "<<last<<endl;
if(p.sc==-1){
while(m>p.fi){
++tsz;
if(a[m]==1) rs[tsz] = last;
else ls[tsz] = last;
last = tsz;
m--;
}
}else{
ll len = p.sc;
ll r = m-1,l = m-len;
ll curlast = ++tsz;
ll en = curlast;
r--;
while(r>=l){
++tsz;
if(a[r]==1) rs[tsz] = curlast;
else ls[tsz] = curlast;
curlast = tsz;
r--;
}
r = m;
if(a[m]==1) rs[en] = curlast,ls[en] = last;
else ls[en] = curlast,rs[en] = last;
last = curlast;
/**
ll poc = tsz;
ll r = m+1;
while(r<i&&a[l]==a[r]){
l++;
r++;
}
if(a[l]!=a[r]){
if(a[r]==1) rs[tsz] = last;
else ls[tsz] = last;
}
last = nlast;
**/
}
m = p.fi;
}
vector<ll> b,c;
for(ll i = 1;i<=tsz;i++){
ll x = tsz-i+1;
ll valb = 0,valc = 0;
if(ls[x]!=0) valb = tsz-ls[x];
if(rs[x]!=0) valc = tsz-rs[x];
b.pb(valb);
c.pb(valc);
}
//dbg(tsz);
//cer(b);
//cer(c);
ll x = Query(tsz,b,c);
//dbg(x);
//dbg(b.back());
if(x==b.back()) a[i] = 0;
else a[i] = 1;
for(ll i = 0;i<=tsz;i++) ls[i] = rs[i] = 0;
tsz = 0;
}
lol:;
if(i>1){
i--;
for(ll l = i;l>=0;l--){
ll len = i-l+1;
if(a[l]==a[i+1]) continue;
for(ll l2 = l;l2>=0;l2-=len){
if(get(l2,l2+len-1)==get(l,i)){
if(l2==l) continue;
ll val = (l2>0?dp[l2-1]:0);
if(val+len<dp[i+1]){
dp[i+1] = val+len;
opt[i+1] = {l2-1,len};
}
}else break;
}
}
i++;
}
hsh[i] = add(mul(hsh[i-1],p),a[i]);
dp[i] = llinf;
for(ll l = i;l>=0;l--){
ll val = (l>0?dp[l-1]:0);
if(val+i-l+1<dp[i]){
dp[i] = val+i-l+1;
opt[i] = {l-1,-1};
}
}
}
ceri(dp,1,n);
string ans;
for(ll i = 0;i<n;i++) ans+=('0'+a[i]);
//ceri(a,0,n-1);
//dbg(ans);
return ans;
}
/**
3
110
10
1001101011
**/
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||