oj.uz

Submission #845605

# Submission time Handle Problem Language Result Execution time Memory
845605 2023-09-06T14:26:50 Z vjudge1 Konstrukcija (COCI20_konstrukcija) C++17
30 / 110
 2 ms 600 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;
  }
  if(k == 0){
    cout<<2<<" "<<0<<endl;
    return 0;
  }

  int nnode = 1;
  vector<pair<int, int> > adj;
  vector<int> waitlist;
  int ak = abs(k);

  if(k > 0){
    ak++;
  while(ak--){
    if(k > 0){
        nnode++;
        adj.pb({1, nnode});
        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;
  }
  }
  else{
     map<int, int> mp;
     int x = (ak+4)/2;
     while(x--){
        adj.pb({1, nnode+1});
        mp[nnode+1] = 1;
        adj.pb({nnode+1, nnode+2});
        waitlist.pb(nnode+2);
        nnode += 2;
        ak++;
     }
     ak -= 1;

     for(int i = 2; i < nnode; i += 2){
        for(auto itr: waitlist){
            if(itr == i+1) continue;
            adj.pb({i, itr});
            ak--;
            if(ak == 0) break;
        }
        if(ak == 0) break;
     }

     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
15.0 / 15.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct.
2 Correct 0 ms 348 KB Correct.
3 Correct 0 ms 348 KB Correct.
4 Correct 0 ms 344 KB Correct.
5 Correct 1 ms 344 KB Correct.
6 Correct 1 ms 344 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 0 ms 348 KB Correct.
9 Correct 0 ms 344 KB Correct.
10 Correct 1 ms 344 KB Correct.
11 Incorrect 2 ms 600 KB Integer parameter [name=N] equals to 4877, violates the range [1, 1000]
12 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct.
2 Correct 0 ms 348 KB Correct.
3 Correct 0 ms 348 KB Correct.
4 Correct 0 ms 344 KB Correct.
5 Correct 1 ms 344 KB Correct.
6 Correct 1 ms 344 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 0 ms 348 KB Correct.
9 Correct 0 ms 344 KB Correct.
10 Correct 1 ms 344 KB Correct.
11 Incorrect 2 ms 600 KB Integer parameter [name=N] equals to 4877, violates the range [1, 1000]
12 Halted 0 ms 0 KB -