Submission #247363

#	Time	Username	Problem	Language	Result	Execution time	Memory
247363		dvdg6566	Konstrukcija (COCI20_konstrukcija)	C++14	110 / 110	6 ms	432 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
typedef long double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end() 
#define SZ(x) (ll)x.size()
#define f first
#define s second
const ll MAXN=63;
// const ll MAXK=100000;
const ll INF = 1e9;
const ll MOD = 1e9+7;

ll N,M,K,Q,R,C,a,b,c,OX;
vi V[MAXN];
vpi edge;
vi toend;

void insrt(ll x){
	ll curn=C;++C;
	edge.pb(1,curn);
	if(x==0){
		toend.pb(curn);
		return;
	}
	else{
		for(auto t:V[x]){
			edge.pb(curn, t);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>K;
	if(K==0){
		// construction for zero
		cout<<"3 2\n1 2\n2 3\n";
		return 0;
	}else if (K==1){
		cout<<"4 4\n1 2\n1 3\n2 4\n3 4\n";
		return 0;
	}
	ll big=-1;
	for(ll i=0;i<MAXN;++i)if((1LL<<i)&abs(K))big=i;
	// begin construction for size big
	C=2;
	if(K<0){
		++big;
		if(big%2==0){V[big+1].pb(1);}
		else{
			V[big+2].pb(1);
			V[big+1].pb(2);
			V[big+1].pb(3);
			edge.pb(1,2);
			edge.pb(1,3);
			C=4;
		}
		K+=(1LL<<big);
	}
	else{
		if(big%2==1){V[big+1].pb(1);}
		else{
			V[big+2].pb(1);
			V[big+1].pb(2);
			V[big+1].pb(3);
			edge.pb(1,2);
			edge.pb(1,3);
			C=4;
		}
		K-=(1LL<<big);
	}
	for(ll i=big;i>0;--i){
		V[i].pb(C);
		V[i].pb(C+1);
		V[i].pb(C+2);
		// cout<<"Layer "<<i<<" having "<<C<<' '<<C+1<<' '<<C+2<<'\n';
		for(auto j:V[i+1])for(auto k:V[i]){
			edge.pb(j,k);
		}
		C+=3;
	}
	for(auto i:V[1])toend.pb(i);
	// cout<<K<<'\n';

	for(ll i=0;i<big;++i)if((1LL<<i)&K){
		if(i%2==0){
			insrt(i);
		}else{
			insrt(i);
			insrt(i+1);
		}
	}

	V[0].pb(C);
	for(auto x:toend)edge.pb(x, C);
	M=SZ(edge);
	cout<<C<<' '<<M<<'\n';
	for(auto i:edge)cout<<i.f<<' '<<i.s<<'\n';
}

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