oj.uz

Submission #478988

# Submission time Handle Problem Language Result Execution time Memory
478988 2021-10-09T10:37:22 Z inksamurai Konstrukcija (COCI20_konstrukcija) C++17
110 / 110
 2 ms 592 KB 
#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.0 / 15.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
20.0 / 20.0

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

Subtask #4
60.0 / 60.0

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