oj.uz

Submission #478792

# Submission time Handle Problem Language Result Execution time Memory
478792 2021-10-08T11:43:43 Z inksamurai Konstrukcija (COCI20_konstrukcija) C++17
15 / 110
 1 ms 588 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 _3ioVv0Q ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
//eodefine
using namespace std;
typedef long long ll;
typedef long double ld;
using pii=pair<int,int>;
using vi=vec(int);
const int mxn=12000;

int main(){
_3ioVv0Q;
	ll k;
	cin>>k;
	const int root=0;
	int nodes=1;
	vec(vi) adj(mxn);
	auto push=[&](int u,int v){
		adj[u].pb(v);
	};
	int magical=mxn;
	auto f=[&](int x){
		vi parent={-1,-1,-1};
		while(x>0){
			rep(t,3){
				if(parent[0]==-1){
					push(root,nodes);
				}else{
					rep(ot,3){
						push(parent[ot],nodes);
					}
				}
				nodes++;
			}
			parent={nodes-1,nodes-2,nodes-3};
			x=x-1;
		}
		if(parent[0]!=-1){
			rep(t,3){
				push(parent[t],magical);
			}
		}else{
			push(root,magical);
		}
	};
	int cmps=0;
	if(k>0){
		push(0,nodes);
		nodes++;
		push(0,nodes);
		push(nodes,magical);
		push(nodes-1,magical);
		nodes++;
		int now=1;
		while(now<k){
			drep(j,30){
				if(j%2 or j==0){
					if(now+(1<<j)+1<=k){
						if(j==0){
							push(0,nodes);
							nodes++;
							push(0,nodes);
							push(nodes,magical);
							push(nodes-1,magical);
							nodes++;
						}else{
							f(j);
						}
						now+=(1<<j)+1;
					}
				}else{
					if(now+(1<<j)+2<=k){
						f(j-1);
						f(j-1);
						now+=(1<<j)+2;
					}
				}
			}
			if(now+1<=k){
				push(0,nodes);
				push(nodes,magical);
				nodes++;
				now++;
			}
		}	
	}else{
		push(0,nodes);
		nodes++;
		push(0,nodes);
		push(nodes,magical);
		push(nodes-1,magical);
		nodes++;
		int now=1;
		while(now>k){
			drep(j,30){
				if(j%2){
					if(now-(1<<j)+2>=k){
						f(j-1);
						f(j-1);
						now-=(1<<j);
						now+=2;
					}
				}else if(j>0){
					if(now-(1<<j)+1>=k){
						f(j);
						now-=(1<<j);
						now+=1;
					}
				}
			}
			if(now-1>=k){
				push(0,nodes);
				push(nodes,magical);
				nodes++;
				push(0,nodes);
				push(nodes,magical);
				nodes++;
				f(2);
				now--;
			}
			// cout<<now<<"\n";
		}	
	}
	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;
}

Compilation message

konstrukcija.cpp: In function 'int main()':
konstrukcija.cpp:59:6: warning: unused variable 'cmps' [-Wunused-variable]
   59 |  int cmps=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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 588 KB Wrong output format.
2 Halted 0 ms 0 KB -

Subtask #3
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 Incorrect 1 ms 588 KB Wrong output format.
7 Halted 0 ms 0 KB -

Subtask #4
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 Incorrect 1 ms 588 KB Wrong output format.
7 Halted 0 ms 0 KB -