| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1056963 | TimDee | Floppy (RMI20_floppy) | C++17 | 0 ms | 0 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 "floppy.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
const int maxn=2e5+5;
int l[maxn],r[maxn];
string s;
void dfs(int u, int p) {
//cout<<"> "<<u<<' '<<p<<' '<<s<<'\n';
if (l[u]!=-1) {
if (p==1) s+="00";
else s+="0";
dfs(l[u],0);
}
if (r[u]!=-1) {
if (p==0) s+="10";
else s+="1";
dfs(r[u],1);
}
if (p==0) s+="11";
if (p==1) s+="01";
}
void read_array(int zzzzz, vector<int>&a) {
int n=a.size();
vector<int> p(n,-1);
int rt=0;
forn(i,n) l[i]=r[i]=-1;
deque<int> st = {0};
for(int i=1; i<n; ++i) {
if (a[i]>a[rt]) {
p[rt]=i;
rt=i;
st.clear();
st.push_back(rt);
continue;
}
if (a[i]<a[st.back()]) {
p[i]=st.back();
st.push_back(i);
continue;
}
int last=-1;
while (a[i]>a[st.back()]) {
last=st.back();
st.pop_back();
}
p[last]=i;
p[i]=st.back();
st.push_back(i);
}
forn(i,n) if (i!=rt) {
if (i<p[i]) l[p[i]]=i;
else r[p[i]]=i;
}
dfs(rt,-1);
cout<<"? "<<s<<'\n';
save_to_floppy(s);
}
struct sgt {
vector<int> t;
vector<int> a;
int sz;
int merge(int i, int j) {
if (i==-1) return j;
if (j==-1) return i;
return a[i]<=a[j]?i:j;
}
sgt(int n) {
sz=1; while (sz<n) sz<<=1; t.assign(2*sz-1,0);
forn(i,n) a.push_back(1e9);
forn(i,n) t[sz-1+i]=i;
}
int query(int v, int l, int r, int lx, int rx) {
if (rx<=l || r<=lx) return -1;
if (lx<=l && r<=rx) return t[v];
int m=(l+r)>>1;
return merge(query(2*v+1,l,m,lx,rx),query(2*v+2,m,r,lx,rx));
}
int query(int l, int r) {
return query(0,0,sz,l,r);
}
void upd(int v, int l, int r, int i) {
if (r-l==1) return;
int m=(l+r)>>1;
if (i<m) upd(2*v+1,l,m,i);
else upd(2*v+2,m,r,i);
t[v]=merge(t[2*v+1],t[2*v+2]);
}
void set(int i, int x) {
a[i]=x;
upd(0,0,sz,i);
}
};
vector<int> solve_queries(int zzzzz, int n, string&s, vector<int>&l, vector<int>&r) {
int m=s.size();
int d=0;
vector<int> a;
int p=0;
char last;
string q;
int from=-1;
while (s[p]=='1') {
a.push_back(d);
q+="1";
++d;
++p;
}
if (!p) {
q+="0";
++d;
++p;
}
while (p<m) {
//cout<<"? "<<p<<' '<<d<<" "<<q<<'\n';
if (s[p]==q.back()) {
if (s[p]=='1') {
a.push_back(d);
}
q+=s[p];
++d;
++p;
from=-1;
} else {
if (s[p+1]=='1') {
if (from!=1) a.push_back(d);
--d;
p+=2;
from=q.back()=='1';
q.pop_back();
} else {
if (s[p]=='1') {
a.push_back(d);
}
++d;
q+=s[p];
p+=2;
from=-1;
}
}
}
sgt st(n);
forn(i,n) st.set(i,a[i]);
vector<int> ans;
forn(i,l.size()) {
ans.push_back(st.query(l[i],r[i]+1));
}
return ans;
//for(auto&x:a) cout<<x<<' '; cout<<'\n'; exit(0);
}