| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1057000 |
2024-08-13T13:02:44 Z |
TimDee |
Floppy (RMI20_floppy) |
C++17 |
|
62 ms |
10700 KB |
#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, const 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'; exit(0);
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, const string&s, const vector<int>&l, const 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'; cout.flush();
if (!q.size()) {
while (s[p]=='1') {
a.push_back(d);
q+="1";
++d;
++p;
}
}
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;
}
}
}
if (a.size()<n) a.push_back(0);
//for(auto&x:a) cout<<x<<' '; cout<<'\n'; exit(0);
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;
}
Compilation message
floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:151:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
151 | if (a.size()<n) a.push_back(0);
| ~~~~~~~~^~
floppy.cpp:5:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
5 | #define forn(i,n) for(int i=0;i<n;++i)
......
156 | forn(i,l.size()) {
| ~~~~~~~~~~
floppy.cpp:156:5: note: in expansion of macro 'forn'
156 | forn(i,l.size()) {
| ^~~~
floppy.cpp:101:10: warning: unused variable 'last' [-Wunused-variable]
101 | char last;
| ^~~~
stub.cpp: In function 'void run2()':
stub.cpp:101:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
101 | if (query_answers.size() != M) {
| ~~~~~~~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
808 KB |
Output is correct |
| 2 |
Correct |
0 ms |
816 KB |
Output is correct |
| 3 |
Correct |
2 ms |
816 KB |
Output is correct |
| 4 |
Correct |
1 ms |
808 KB |
Output is correct |
| 5 |
Correct |
0 ms |
920 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
3132 KB |
Output is correct |
| 2 |
Correct |
15 ms |
3036 KB |
Output is correct |
| 3 |
Correct |
16 ms |
3344 KB |
Output is correct |
| 4 |
Correct |
15 ms |
3148 KB |
Output is correct |
| 5 |
Correct |
15 ms |
3144 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
57 ms |
9916 KB |
Partially correct |
| 2 |
Partially correct |
59 ms |
9724 KB |
Partially correct |
| 3 |
Partially correct |
60 ms |
10700 KB |
Partially correct |
| 4 |
Partially correct |
60 ms |
10160 KB |
Partially correct |
| 5 |
Partially correct |
62 ms |
9680 KB |
Partially correct |
