oj.uz

답안 #247331

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
247331 2020-07-11T08:47:19 Z dvdg6566 Konstrukcija (COCI20_konstrukcija) C++14
15 / 110
 5 ms 512 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&K)big=i;
	// begin construction for size big
	C=2;
	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;
	}
	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);
	K-=(1<<big);
	// cout<<K<<'\n';

	for(ll i=0;i<big;++i)if((1<<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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Correct.
2 Correct 5 ms 384 KB Correct.
3 Correct 5 ms 384 KB Correct.
4 Correct 5 ms 384 KB Correct.
5 Correct 5 ms 384 KB Correct.

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Correct.
2 Correct 5 ms 384 KB Correct.
3 Correct 5 ms 384 KB Correct.
4 Correct 5 ms 384 KB Correct.
5 Correct 5 ms 384 KB Correct.
6 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Correct.
2 Correct 5 ms 384 KB Correct.
3 Correct 5 ms 384 KB Correct.
4 Correct 5 ms 384 KB Correct.
5 Correct 5 ms 384 KB Correct.
6 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -