/**
* user: turevskii-2c9
* fname: Maxim
* lname: Turevskii
* task: Floppy
* score: 64.0
* date: 2020-12-03 10:10:39.759270
*/
#include <bits/stdc++.h>
#include "floppy.h"
using namespace std;
/*string o1;
void save_to_floppy(string bits)
{
o1=bits;
}*/
void read_array(int id,const vector <int> &v)
{
int n=v.size();
vector <pair<int,int> > z1;
for(int i=0;i<n;++i)
{
z1.push_back({v[i],i});
}
sort(z1.begin(),z1.end());
vector <int> t(n);
int curr=(-1);
for(int i=0;i<z1.size();++i)
{
if(i==0 || z1[i].first!=z1[i-1].first)
{
++curr;
t[z1[i].second]=curr;
}
else
{
t[z1[i].second]=curr;
}
}
int nxt[n];int prev[n];bool used[n];
for(int i=0;i<n;++i)
{
nxt[i]=(i+1);prev[i]=(i-1);used[i]=false;
}
vector <int> h(n);
vector <int> z;
int cyc=(-1);
int prev1[n],nxt1[n];
vector <int> g;
vector <int> f;
for(int i=0;i<n;++i)
{
f.push_back(i);
}
vector <int> f1;
while(true)
{
f1.clear();
g.clear();
++cyc;
int curr=0;
if(used[curr])
{
z.clear();
int o2=nxt[curr];
z.clear();
z.push_back(curr);
while(true)
{
if(o2==n) break;
if(!used[o2]) break;
z.push_back(o2);
o2=nxt[o2];
}
for(auto h1:z)
{
nxt[h1]=o2;
}
curr=o2;
}
if(curr==n) break;
//cout<<curr<<" curr "<<endl;
for(auto i:f)
{
if(i>=0 && i<n && !used[i]) {}
else {continue;}
//cout<<i<<" i "<<endl;
int o1=prev[i];
//cout<<o1<<" o1 "<<endl;
z.clear();
z.push_back(i);
while(true)
{
if(o1==(-1)) break;
if(!used[o1]) break;
z.push_back(o1);
o1=prev[o1];
}
for(auto h1:z)
{
prev[h1]=o1;
}
int o2=nxt[i];
z.clear();
z.push_back(i);
while(true)
{
if(o2==n) break;
if(!used[o2]) break;
z.push_back(o2);
o2=nxt[o2];
}
for(auto h1:z)
{
nxt[h1]=o2;
}
if((o1==(-1) || (t[o1]>=t[i] && !used[i])) && (o2==n || (t[o2]>=t[i] && !used[i])))
{
g.push_back(i);
h[i]=cyc;
prev1[i]=o1;nxt1[i]=o2;
}
}
for(auto u:g)
{
int i=u;
int o1=prev[i];
//cout<<o1<<" o1 "<<endl;
z.clear();
z.push_back(i);
while(true)
{
if(o1==(-1)) break;
if(!used[o1]) break;
z.push_back(o1);
o1=prev[o1];
}
for(auto h1:z)
{
prev[h1]=o1;
}
int o2=nxt[i];
z.clear();
z.push_back(i);
while(true)
{
if(o2==n) break;
if(!used[o2]) break;
z.push_back(o2);
o2=nxt[o2];
}
for(auto h1:z)
{
nxt[h1]=o2;
}
f1.push_back(prev[u]);f1.push_back(nxt[u]);
used[u]=true;
}
sort(f1.begin(),f1.end());
f1.erase(unique(f1.begin(),f1.end()),f1.end());
f=f1;
}
/*for(auto l:h)
{
cout<<l<<' ';
}
cout<<endl;*/
string bits1,bits2;
for(int i=0;i<n;++i)
{
if(h[i]==0) bits1+='1';
else bits1+='0';
//cout<<prev1[i]<<' '<<nxt1[i]<<endl;
if(prev1[i]!=(-1) && h[prev1[i]]==(h[i]+1)) bits2+="10";
else if(nxt1[i]!=n && h[nxt1[i]]==(h[i]+1)) bits2+="11";
else bits2+="00";
}
bits1+=bits2;
save_to_floppy(bits1);
}
const int maxn=40005;
pair <int,int> t[4*maxn];
pair <int,int> merg(pair <int,int> u,pair <int,int> v)
{
if(u.first<=v.first)
{
return u;
}
else
{
return v;
}
}
void to(int node,int tl,int tr,int pos,int val)
{
if(tl>pos || tr<=pos)
{
return;
}
if((tr-tl)==1)
{
t[node]={-val,tl};
return;
}
int tm=(tl+tr)/2;
to(2*node+1,tl,tm,pos,val);to(2*node+2,tm,tr,pos,val);
t[node]=merg(t[2*node+1],t[2*node+2]);
}
pair <int,int> get(int node,int tl,int tr,int l,int r)
{
if(tl>=l && tr<=r)
{
return t[node];
}
if(tl>=r || tr<=l)
{
return {1e9,1e9};
}
int tm=(tl+tr)/2;
return merg(get(2*node+1,tl,tm,l,r),get(2*node+2,tm,tr,l,r));
}
vector <int> solve_queries(int id,int n,const string &bits,const vector <int> &a,const vector <int> &b)
{
vector <int> v;
for(int i=0;i<n;++i)
{
if(bits[i]=='1') v.push_back(i);
}
int nxt[n];int prev[n];bool used[n];
for(int i=0;i<n;++i)
{
nxt[i]=(i+1);prev[i]=(i-1);used[i]=false;
}
vector <int> v1;
vector <int> z;
vector <int> o(n);
int cyc=(-1);
while(!v.empty())
{
v1.clear();
++cyc;
for(auto i:v)
{
o[i]=cyc;
used[i]=true;
if(bits[2*i+n]=='1' && bits[2*i+n+1]=='1')
{
int o2=nxt[i];
z.clear();
z.push_back(i);
while(true)
{
if(o2==n) break;
if(!used[o2]) break;
z.push_back(o2);
o2=nxt[o2];
}
for(auto h1:z)
{
nxt[h1]=o2;
}
if(o2!=n)
v1.push_back(o2);
}
else if(bits[2*i+n]=='1' && bits[2*i+n+1]=='0')
{
int o1=prev[i];
z.clear();
z.push_back(i);
while(true)
{
if(o1==(-1)) break;
if(!used[o1]) break;
z.push_back(o1);
o1=prev[o1];
}
for(auto h1:z)
{
prev[h1]=o1;
}
if(o1!=(-1))
v1.push_back(o1);
}
else {}
}
sort(v1.begin(),v1.end());
v1.erase(unique(v1.begin(),v1.end()),v1.end());
v=v1;
}
for(int i=0;i<o.size();++i)
{
to(0,0,maxn,i,o[i]);
}
//cout<<get(0,0,maxn,0,1).first<<' '<<get(0,0,maxn,0,1).second<<" get "<<endl;
/*for(auto l:o)
{
cout<<l<<' ';
}
cout<<endl;*/
vector <int> res(a.size());
for(int i=0;i<a.size();++i)
{
int l=a[i];
int r=b[i];
pair <int,int> u=get(0,0,maxn,l,r+1);
res[i]=u.second;
}
return res;
}
/*int32_t main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
read_array(0,{1,2,3,6,6,5,2,3,5,6});
//vector <int> a={0,1},b={5,6};
//vector <int> res=solve_queries(0,9,o1,a,b);
//for(auto h:res) cout<<h<<' ';
return 0;
}*/
Compilation message
floppy.cpp: In function 'void read_array(int, const std::vector<int>&)':
floppy.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for(int i=0;i<z1.size();++i)
| ~^~~~~~~~~~
floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:290:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
290 | for(int i=0;i<o.size();++i)
| ~^~~~~~~~~
floppy.cpp:301:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
301 | for(int i=0;i<a.size();++i)
| ~^~~~~~~~~
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) {
| ~~~~~~~~~~~~~~~~~~~~~^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
772 KB |
Output is correct |
| 2 |
Correct |
3 ms |
768 KB |
Output is correct |
| 3 |
Correct |
3 ms |
776 KB |
Output is correct |
| 4 |
Correct |
4 ms |
768 KB |
Output is correct |
| 5 |
Correct |
3 ms |
776 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
39 ms |
3364 KB |
Output is correct |
| 2 |
Correct |
38 ms |
3344 KB |
Output is correct |
| 3 |
Correct |
42 ms |
3248 KB |
Output is correct |
| 4 |
Correct |
39 ms |
3296 KB |
Output is correct |
| 5 |
Correct |
38 ms |
3280 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Partially correct |
168 ms |
11320 KB |
Partially correct |
| 2 |
Partially correct |
154 ms |
11320 KB |
Partially correct |
| 3 |
Partially correct |
150 ms |
11184 KB |
Partially correct |
| 4 |
Partially correct |
158 ms |
11548 KB |
Partially correct |
| 5 |
Partially correct |
152 ms |
11252 KB |
Partially correct |
