Submission #478988

#	Time	Username	Problem	Language	Result	Execution time	Memory
478988		inksamurai	Konstrukcija (COCI20_konstrukcija)	C++17	110 / 110	2 ms	592 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) (int)(c).size()
#define make_unique(a) sort(all(a)),a.erase(unique(all(a)),a.end());
#define rep(i,n) for(int i=0;i<n;i++)
#define drep(i,n) for(int i=n-1;i>=0;i--)
#define crep(i,x,n) for(int i=x;i<n;i++)
#define vec(...) vector<__VA_ARGS__>
#define _3ApxLzO ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
//eodefine
using namespace std;
typedef long long i64;
typedef long double ld;
using pii=pair<int,int>;
using tpii=pair<int,pii>;
using vi=vec(int);
const int mxn=12000;

int main(){
_3ApxLzO;
	i64 k;
	cin>>k;
	vec(vi) adj(mxn);
	auto push=[&](int u,int v){
		adj[u].pb(v);
	};
	vec(vi) stars(62);
	int magical=mxn;
	int nodes=1,root=0;
	auto construct=[&](int x){
		vi parent;
		rep(t,3){
			parent.pb(-1);
		}
		while(x>0){
			rep(t,3){
				if(parent[0]==-1){
					push(root,nodes);
				}else{
					rep(ot,3){
						push(parent[ot],nodes);
					}
				}
				stars[x].pb(nodes);
				nodes++;
			}
			parent.clear();
			rep(t,3){
				parent.pb(nodes-(t+1));
			}
			x=x-1;
		}
		rep(t,3){
			push(parent[t],magical);
		}
	};
	int hbit=-1;
	drep(j,61){
		if(abs(k)&(1ll<<j)){
			construct(j);
			hbit=j;
			break;
		}
	}
	if((k>0 and hbit%2==0) or (k<0 and hbit%2!=0)){
		rep(t,2){
			push(0,nodes);
			for(auto x : stars[hbit]){
				push(nodes,x);
			}
			nodes++;
		}
	}
	drep(j,hbit){
		if(abs(k)&(1ll<<j)){
			bool swp=0;
			if(j%2!=0 and k>0) swp=1;
			if(j%2==0 and k<0) swp=1;
			if(swp){
				if(j==1){
					rep(t,2){
						push(0,nodes);
						push(nodes,magical);
						nodes++;
					}
				}else if(j==0 and k<0){
					// rep(t,2){
					push(0,nodes);
					for(auto x : stars[1]){
						push(nodes,x);
					}
					nodes++;
					// }
					push(0,nodes);
					push(nodes,magical);
					nodes++;
				}else{
					rep(t,2){
						push(0,nodes);
						for(auto x : stars[j-1]){
							push(nodes,x);
						}
						nodes++;
					}
				}
			}else{
				if(j==0){
					push(0,nodes);
					push(nodes,magical);
					nodes++;
				}else{
					push(0,nodes);
					for(auto x : stars[j]){
						push(nodes,x);
					}
					nodes++;
				}
			}
		}
	}
	int m=0;
	rep(v,mxn){
		m+=sz(adj[v]);
	}
	cout<<nodes+1<<" "<<m<<"\n";
	rep(i,mxn){
		int 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: 60 / 60