Submission #478814

#	Time	Username	Problem	Language	Result	Execution time	Memory
478814		inksamurai	Konstrukcija (COCI20_konstrukcija)	C++17	50 / 110	3 ms	716 KiB

Main

#include <bits/stdc++.h>
//eolibraries
#define lnf 3999999999999999999
#define inf 999999999
#define fi first
#define se second
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define sz(c) (ll)(c).size()
#define make_unique(a) sort(all(a)),a.erase(unique(all(a)),a.end());
#define rep(i,n) for(ll i=0;i<n;i++)
#define drep(i,n) for(ll i=n-1;i>=0;i--)
#define crep(i,x,n) for(ll i=x;i<n;i++)
#define vec(...) vector<__VA_ARGS__>
#define _3ioVv0Q ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
//eodefine
using namespace std;
typedef long long ll;
typedef long double ld;
using pii=pair<ll,ll>;
using tpii=pair<ll,pii>;
using vi=vec(ll);
const ll mxn=12000;

int main(){
_3ioVv0Q;
	ll k;
	cin>>k;
	const ll root=0;
	ll nodes=1;
	vec(vi) adj(mxn);
	auto push=[&](ll u,ll v){
		adj[u].pb(v);
	};
	ll magical=mxn;
	auto f=[&](ll x,ll type){
		vi parent;
		rep(t,type+1){
			parent.pb(-1);
		}
		while(x>0){
			rep(t,type+1){
				if(parent[0]==-1){
					push(root,nodes);
				}else{
					rep(ot,type+1){
						push(parent[ot],nodes);
					}
				}
				nodes++;
			}
			parent.clear();
			rep(t,type+1){
				parent.pb(nodes-(t+1));
			}
			x=x-1;
		}
		if(parent[0]!=-1){
			rep(t,type+1){
				push(parent[t],magical);
			}
		}else{
			push(root,magical);
		}
	};
	push(0,nodes);
	nodes++;
	push(0,nodes);
	push(nodes,magical);
	push(nodes-1,magical);
	nodes++;
	ll now=1;
	if(k>0){
		vec(tpii) candies;
		crep(x,2,9){
			ll nowval=1;
			rep(j,60){
				if(nowval>k) break;
				if(j%2){
					candies.pb({nowval+1,{x,j}});
				}
				nowval*=x;
			}
		}
		sort(all(candies));
		reverse(all(candies));
		while(now<k){
			rep(j,sz(candies)){
				ll val=candies[j].fi;
				ll type=candies[j].se.fi;
				ll x=candies[j].se.se;
				if(now+val<=k){
					now+=val;
					f(x,type);
				}
			}
			if(now+1<=k){
				push(0,nodes);
				push(nodes,magical);
				nodes++;
				now++;
			}
		}
	}else{	
		vec(tpii) candies;
		crep(x,2,9){
			ll nowval=1;
			rep(j,60){
				if(nowval>abs(k)) break;
				if(j%2==0 and j>0){
					candies.pb({nowval-1,{x,j}});
				}
				nowval*=x;
			}
		}
		sort(all(candies));
		reverse(all(candies));
		while(now>k){
			rep(j,sz(candies)){
				ll val=candies[j].fi;
				ll type=candies[j].se.fi;
				ll x=candies[j].se.se;
				if(now-val>=k){
					now-=val;
					f(x,type);
				}
			}
			if(now-1>=k){
				push(0,nodes);
				push(nodes,magical);
				nodes++;
				push(0,nodes);
				push(nodes,magical);
				nodes++;
				f(2,2);
				now--;
			}
		}
	}
	ll m=0;
	rep(v,mxn){
		m+=sz(adj[v]);
	}
	cout<<nodes+1<<" "<<m<<"\n";
	rep(i,mxn){
		ll v=i;
		for(auto u : adj[i]){
			cout<<(v==magical?nodes:v)+1<<" "<<(u==magical?nodes:u)+1<<"\n";
		}
	}
//	
	return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 0 / 60