/**
* user: lendvaj-c30
* fname: Dorijan
* lname: Lendvaj
* task: Floppy
* score: 46.0
* date: 2020-12-03 08:03:36.811377
*/
#include "floppy.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int,int>
using ll=long long;
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define eb emplace_back
#define all(a) begin(a),end(a);
using namespace std;
const int N=300010,MOD=1e9+7,M=1<<17;
const char en='\n';
const ll LLINF=1ll<<60;
pii seg[M*2+10];
string ans;
void upd(int i,int x)
{
seg[i+=M]={x,i};
for (i/=2;i;i/=2) seg[i]=max(seg[i*2],seg[i*2+1]);
}
pii ge(int l,int r,int lo=0,int hi=M,int i=1)
{
if (lo>=l && hi<=r) return seg[i];
if (lo>=r || hi<=l) return {-MOD,0};
int mid=(lo+hi)/2;
return max(ge(l,r,lo,mid,i*2),ge(l,r,mid,hi,i*2+1));
}
void buildTree(int l,int r)
{
//cout<<l<<' '<<r<<endl;
if (l==r) return;
pii ma=ge(l,r);
int po=ma.y;
ans.pb('0');
buildTree(l,po);
ans.pb('1');
ans.pb('0');
buildTree(po+1,r);
ans.pb('1');
}
void read_array(int subtask_id, const vi &v) {
memset(seg,0,sizeof(seg));
ans.clear();
int n=v.size();
for (int i=0;i<n;++i) upd(i,v[i]);
//cout<<"Tu"<<endl;
buildTree(0,n);
//cout<<"Bits: "<<ans<<endl;
save_to_floppy(ans);
//cout<<"Why is there a segfault here"<<endl;
}
int par[20][N],de[N],id,pl;
string eut;
int trave(int dep)
{
if (eut[pl]=='1')
{
return -1;
}
++pl;
int lc=trave(dep+1);
int i=id++;
++pl;
++pl;
int rc=trave(dep+1);
++pl;
if (lc!=-1) par[0][lc]=i;
if (rc!=-1) par[0][rc]=i;
par[0][i]=i;
de[i]=dep;
//cout<<i<<' '<<lc<<' '<<rc<<endl;
return i;
}
vi solve_queries(int subtask_id, int N, const string &bits, const vi &a, const vi &b) {
int n=N;
eut=bits;
id=pl=0;
memset(par,0,sizeof(par));
trave(0);
assert(pl==eut.size());
assert(id==n);
//for (int i=0;i<n;++i) cout<<par[0][i]<<' ';
//cout<<en;
for (int j=1;j<=18;++j) for (int i=0;i<n;++i) par[j][i]=par[j-1][par[j-1][i]];
int m=a.size();
vi answers;
for (int q=0;q<m;++q)
{
int l=a[q],r=b[q];
for (int i=18;i>=0;--i) if (de[l]-de[r]>=(1<<i)) l=par[i][l];
for (int i=18;i>=0;--i) if (de[r]-de[l]>=(1<<i)) r=par[i][r];
for (int i=18;i>=0;--i) if (par[i][l]!=par[i][r]) l=par[i][l],r=par[i][r];
if (l!=r) l=par[0][l],r=par[0][r];
assert(l==r);
answers.pb(l);
//cout<<l<<en;
}
//cout<<endl;
return answers;
}
Compilation message
In file included from /usr/include/c++/9/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
from floppy.cpp:10:
floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:100:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | assert(pl==eut.size());
| ~~^~~~~~~~~~~~
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 |
13 ms |
26232 KB |
Output is correct |
| 2 |
Correct |
13 ms |
26244 KB |
Output is correct |
| 3 |
Correct |
13 ms |
26244 KB |
Output is correct |
| 4 |
Correct |
15 ms |
26304 KB |
Output is correct |
| 5 |
Correct |
13 ms |
26300 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
28100 KB |
Output is correct |
| 2 |
Correct |
48 ms |
28208 KB |
Output is correct |
| 3 |
Correct |
48 ms |
28856 KB |
Output is correct |
| 4 |
Correct |
53 ms |
28572 KB |
Output is correct |
| 5 |
Correct |
61 ms |
28088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
181 ms |
34232 KB |
Partially correct |
| 2 |
Partially correct |
167 ms |
34240 KB |
Partially correct |
| 3 |
Partially correct |
224 ms |
37224 KB |
Partially correct |
| 4 |
Partially correct |
185 ms |
35580 KB |
Partially correct |
| 5 |
Partially correct |
187 ms |
34180 KB |
Partially correct |
