oj.uz

Submission #845459

# Submission time Handle Problem Language Result Execution time Memory
845459 2023-09-06T13:41:23 Z vjudge1 Konstrukcija (COCI20_konstrukcija) C++17
0 / 110
 1 ms 348 KB 
#include <bits/stdc++.h>
#define endl "\n"
#define pb push_back
#define int long long
using namespace std;

const int inf = 2e18 + 5;
const int N = 5e3 + 5;
const int mod = 998244353;

int fpow(int a, int b){
 if(b == 0) return 1;

 int p = 1;
 while(b){
    if(b&1) p = p*a;

    b = b/2;
    a = a*a;
 }

 return p;
}

int32_t main(){
  //freopen("in.txt","r", stdin);
  int k;
  cin>>k;
  if(k == 1){
    cout<<1<<" "<<0<<endl;
    return 0;
  }
  int nnode = 1;
  vector<pair<int, int> > adj;
  vector<int> waitlist;

  int ak = abs(k);
  if(ak&1){
     adj.pb({1, nnode+1});
     waitlist.pb(nnode+1);
     nnode++;
  }

  for(int i = 1; i < 30; i++){
    if(fpow(2, i)&ak){
        if(k > 0){
            adj.pb({1, nnode+1});
            nnode++;
            for(int j = 0; j < i; j++){
               adj.pb({nnode, nnode+1});
               adj.pb({nnode, nnode+2});
               adj.pb({nnode+1, nnode+3});
               adj.pb({nnode+2, nnode+3});
               nnode += 3;
            }
            waitlist.pb(nnode);
        }
        else{
            adj.pb({1, nnode+1});
            adj.pb({1, nnode+2});
            adj.pb({nnode+1, nnode+3});
            adj.pb({nnode+2, nnode+3});
            nnode += 3;
            for(int j = 0; j < i-1; j++){
               adj.pb({nnode, nnode+1});
               adj.pb({nnode, nnode+2});
               adj.pb({nnode+1, nnode+3});
               adj.pb({nnode+2, nnode+3});
               nnode += 3;
            }
            waitlist.pb(nnode);
        }
    }
  }

  cout<<nnode+1<<" "<<adj.size() + waitlist.size()<<endl;
  for(auto itr: adj) cout<<itr.first<<" "<<itr.second<<endl;
  for(auto itr: waitlist) cout<<itr<<" "<<nnode+1<<endl;
  return 0;
}

Subtask #1
0 / 15.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 60.0

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