Submission #69994

#	Time	Username	Problem	Language	Result	Execution time	Memory
69994		khohko	Zalmoxis (BOI18_zalmoxis)	C++17	100 / 100	272 ms	34956 KiB

zalmoxis

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
#define MAX ((ll)(1e12+100))
#define MX ((ll)(1e6+100))
#define ARRS ((ll)(2e6+100))
#define HS ((ll)(233))
#define MOD ((ll)(1e9+7))
#define EP ((double)(1e-9))
#define LG 21
#define mul(a,b) a=((a)*(b))%MOD
using namespace std;
ll a[ARRS];
ll f[ARRS];
ll n;
vector<ll> v;

ll go(ll x,ll i){
	if(x==a[i]){v.pb(x);return i+1;}
	//if(x>a[i]){
	i=go(x-1,i);
	if(x<=a[i]||i==n){
		f[v.size()]=1;
		v.pb(x-1);
	}
	else
		i=go(x-1,i);
	return i;
	//}
}
vector<ll> pas;
ll splt(ll x,ll k){
	//cout<<x<<" "<<k<<endl;
	ll sk=k;
	if(x==0){pas.pb(0);return 1;}
	if(k==1){pas.pb(x);return 1;}
	k-=splt(x-1,k-1);
	k-=splt(x-1,k);
	return sk-k;
}

int main(){
	#ifdef KHOKHO
		freopen("in.in","r",stdin);
		freopen("out.out","w",stdout);
	#endif // KHOKHO
	ios::sync_with_stdio(0);
	ll k;
	cin>>n>>k;
	for(int i=0; i<n; i++){
		cin>>a[i];
	}
	go(30,0);
	ll ct=0;
	for(int i=0; i<v.size(); i++){
		//cout<<v[i]<<" "<<f[i]<<endl;
		ct+=f[i];
	}
	//k-=v.size()-n;
//	vector<ll> pas;
	for(int i=0; i<v.size(); i++){
		if(f[i])
			k=k-splt(v[i],k-ct+1),ct--;
		else pas.pb(v[i]);
	}
	for(auto x:pas){
		cout<<x<<" ";
	}

}

Compilation message (stderr)

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:59:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++){
               ~^~~~~~~~~
zalmoxis.cpp:65:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++){
               ~^~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70