#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=100;
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(now+(1<<j)+1<=k){
if(j==0){
push(0,nodes);
nodes++;
push(0,nodes);
push(nodes,magical);
push(nodes-1,magical);
nodes++;
}else{
if(j%2){
f(j);
}else{
f(j-1);
f(j-1);
}
}
now+=(1<<j)+1;
}
}
if(now+1<=k){
push(0,nodes);
push(nodes,magical);
nodes++;
now++;
}
}
}
int m=0,n=0;
rep(v,101){
m+=sz(adj[v]);
if(sz(adj[v])) n++;
// for(auto u : adj[v]){
// cout<<v+1<<" "<<u+1<<"\n";
// }
}
cout<<n<<" "<<m<<"\n";
rep(i,101){
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;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
588 KB |
Integer parameter [name=Y_16] equals to 77, violates the range [1, 76] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
588 KB |
Integer parameter [name=N] equals to 0, violates the range [1, 1000] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
588 KB |
Integer parameter [name=Y_16] equals to 77, violates the range [1, 76] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
588 KB |
Integer parameter [name=Y_16] equals to 77, violates the range [1, 76] |
| 2 |
Halted |
0 ms |
0 KB |
- |
