Submission #1157258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157258		hxano	Floppy (RMI20_floppy)	C++20	0 / 100	54 ms	6216 KiB

floppy

#include "floppy.h"
#include <bits/stdc++.h>
#define ll int
#define ii pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define lwb lower_bound
#define upb upper_bound
#define ld double
#define ins insert
#define del erase
#define ull unsigned long long
using namespace std;
const ll big=4e4+9;
const ll inf=1e9;
const ll mod=1e9+7;
const ll hug=3e6;
struct tr{ll fi,se,th; tr(ll _fi=0, ll _se=0, ll _th=0){fi=_fi; se=_se; th=_th;}};
struct qu{ll fi,se,th,fo; qu(ll _fi=0, ll _se=0, ll _th=0, ll _fo=0){fi=_fi; se=_se; th=_th; fo=_fo;}};
ll mxz(ll &t, ll val){if (t<val){t=val; return 1;} return 0;}
ll mnz(ll &t, ll val){if (t>val){t=val; return 1;} return 0;}
ll qpw(ll n, ll k, ll m=mod){ll p=1, t=n%m; while (k){if (k&1) p=p*t%m; t=t*t%m; k>>=1;} return p;}
ll ran(){
	ll s=0;
	for (ll i=0; i<5; ++i) s^=(1ll*rand())<<(i*14ll);
	return abs(s);
}
ll ran(ll l, ll r){
	return ran()%(r-l+1)+l;
}
ll pmn[16][big];
ll a[big];
string s;
ll qmn(ll l, ll r){
	ll t=log2(r-l+1);
	ll L=pmn[t][l], R=pmn[t][r+1-(1ll<<t)];
	return (a[L]>a[R]? L: R);
}
ll calc(ll l, ll r){
	if (l==r){
		s.pb(0); s.pb(0);
		return 0;
	}
	ll p=qmn(l,r);
	if (l<=p-1) s.pb(1); else s.pb(0);
	if (p+1<=r) s.pb(1); else s.pb(0);
	if (l<=p-1) calc(l,p-1);
	if (p+1<=r) calc(p+1,r);
	return 0;
}
void read_array(ll iquifd, const vector<ll> &_a){
	ll n=(ll)_a.size();
	for (ll i=0; i<n; ++i) a[i]=_a[i];
	for (ll i=0; i<n; ++i) pmn[0][i]=i;
	for (ll j=1; (1ll<<j)<=n; ++j) for (ll i=0; i+(1ll<<j)-1<n; ++i){
		ll L=pmn[j-1][i], R=pmn[j-1][i+(1ll<<(j-1))];
		pmn[j][i]=(a[L]>a[R]? L: R);
	}
	s="";
	calc(0,n-1);
	save_to_floppy(s);
	return;
}
ll an=0;
ll tempo=0;
ll dfs(){
	ll val=0;
	char xl=s[2*tempo], xr=s[2*tempo+1];
	if (xl=='1'){
		++tempo;
		mxz(val,dfs());
	}
	ll p=an; ++an;
	if (xr=='1'){
		++tempo;
		mxz(val,dfs());
	}
	a[p]=val+1;
//	cout<<p<<": "<<xl<<xr<<"\n";
	return a[p];
}
vector<ll> solve_queries(ll qownhixe, ll n, const string &_s, const vector<ll> &x, const vector<ll> &y){
	ll q=(ll)x.size();
	vector<ll> ans(x);
	s=_s;
	dfs();
//	for (ll i=0; i<n; ++i) cout<<a[i]<<" "; cout<<"\n";
	for (ll i=0; i<n; ++i) pmn[0][i]=i;
	for (ll j=1; (1ll<<j)<=n; ++j) for (ll i=0; i+(1ll<<j)-1<n; ++i){
		ll L=pmn[j-1][i], R=pmn[j-1][i+(1ll<<(j-1))];
		pmn[j][i]=(a[L]>a[R]? L: R);
	}
	for (ll i=0; i<q; ++i) ans[i]=qmn(x[i],y[i]);
//	for (ll t: ans) cout<<t<<" "; cout<<"\n";
	return ans;
}
//1 5 3 2 6 4
//111100010000
int mainn(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    freopen("INPUT.TXT","r",stdin);
//    freopen("OUTPUT.TXT","w",stdout);
//	ll tst=1;
//	cin>>tst;
//	for (; tst; --tst) solve();
	solve_queries(1,6,"111100010000",{1,2,0,2},{4,5,1,3});
    return 0;
}

Compilation message (stderr)

floppy.cpp: In function 'int mainn()':
floppy.cpp:103:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |     freopen("INPUT.TXT","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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