oj.uz

Submission #247363

# Submission time Handle Problem Language Result Execution time Memory
247363 2020-07-11T08:58:45 Z dvdg6566 Konstrukcija (COCI20_konstrukcija) C++14
110 / 110
 6 ms 432 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Correct.
2 Correct 4 ms 384 KB Correct.
3 Correct 5 ms 384 KB Correct.
4 Correct 4 ms 384 KB Correct.
5 Correct 4 ms 384 KB Correct.

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Correct.
2 Correct 5 ms 384 KB Correct.
3 Correct 5 ms 384 KB Correct.
4 Correct 4 ms 384 KB Correct.
5 Correct 5 ms 384 KB Correct.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Correct.
2 Correct 4 ms 384 KB Correct.
3 Correct 5 ms 384 KB Correct.
4 Correct 4 ms 384 KB Correct.
5 Correct 4 ms 384 KB Correct.
6 Correct 4 ms 384 KB Correct.
7 Correct 5 ms 384 KB Correct.
8 Correct 5 ms 384 KB Correct.
9 Correct 4 ms 384 KB Correct.
10 Correct 5 ms 384 KB Correct.
11 Correct 5 ms 384 KB Correct.
12 Correct 4 ms 384 KB Correct.
13 Correct 5 ms 384 KB Correct.
14 Correct 5 ms 384 KB Correct.
15 Correct 6 ms 384 KB Correct.

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Correct.
2 Correct 4 ms 384 KB Correct.
3 Correct 5 ms 384 KB Correct.
4 Correct 4 ms 384 KB Correct.
5 Correct 4 ms 384 KB Correct.
6 Correct 4 ms 384 KB Correct.
7 Correct 5 ms 384 KB Correct.
8 Correct 5 ms 384 KB Correct.
9 Correct 4 ms 384 KB Correct.
10 Correct 5 ms 384 KB Correct.
11 Correct 5 ms 384 KB Correct.
12 Correct 4 ms 384 KB Correct.
13 Correct 5 ms 384 KB Correct.
14 Correct 5 ms 384 KB Correct.
15 Correct 6 ms 384 KB Correct.
16 Correct 5 ms 384 KB Correct.
17 Correct 5 ms 384 KB Correct.
18 Correct 5 ms 384 KB Correct.
19 Correct 5 ms 384 KB Correct.
20 Correct 5 ms 432 KB Correct.
21 Correct 5 ms 384 KB Correct.
22 Correct 5 ms 384 KB Correct.
23 Correct 5 ms 384 KB Correct.
24 Correct 5 ms 384 KB Correct.
25 Correct 5 ms 384 KB Correct.
26 Correct 5 ms 384 KB Correct.
27 Correct 5 ms 384 KB Correct.