Submission #398510

#	Time	Username	Problem	Language	Result	Execution time	Memory
398510		model_code	Floppy (RMI20_floppy)	C++17	48.82 / 100	224 ms	37224 KiB

floppy

/**
* 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 (stderr)

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) {
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~

• Subtask 1: 7 / 7
• Subtask 2: 21 / 21
• Subtask 3: 20.8150517808 / 72