oj.uz

Submission #212303

# Submission time Handle Problem Language Result Execution time Memory
212303 2020-03-22T16:51:02 Z model_code Konstrukcija (COCI20_konstrukcija) C++14
110 / 110
 5 ms 384 KB 
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " = " << x << endl
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)

typedef long long int llint;

typedef pair<int, int> par;

#define X first
#define Y second

struct graf {
  int n;
  vector<par> bridovi;
  vector<int> zadnji_sloj;
  graf(int _n, vector<par> _bridovi) {
    n = _n;
    bridovi = _bridovi;
  }
  graf() {
    n = 1;
    zadnji_sloj.push_back(1);
  }

  llint puta_minus_dva(llint pref) {
    vector<int> novi = {n + 1, n + 2, n + 3};
    for(auto x : zadnji_sloj)
      for(auto y : novi)
        bridovi.push_back(par(x, y));
    zadnji_sloj = novi;
    n = n + 3;
    return -2 * pref;
  }

  llint oduzmi_jedan(llint pref) {
    bridovi.push_back(par(1, n + 1));
    zadnji_sloj.push_back(n + 1);
    n = n + 1;
    return pref - 1;
  }

  llint dodaj_jedan(llint pref) {
    vector<int> novi = {n + 1, n + 2};
    for(auto x : zadnji_sloj)
      for(auto y : novi)
        bridovi.push_back(par(x, y));
    bridovi.push_back(par(1, n + 3));
    novi.push_back(n + 3);
    zadnji_sloj = novi;
    n = n + 3;
    return -pref - 1; // primijeti: ovo zapravo nije "dodaj 1",
  }                   // ali je u smislu apsolutne vrijenosti

  void zavrsi_isti() {
    vector<int> novi = {n + 1, n + 2};
    for(auto x : zadnji_sloj)
      for(auto y : novi)
        bridovi.push_back(par(x, y));
    zadnji_sloj = novi;
    for(auto x : zadnji_sloj)
      bridovi.push_back(par(x, n + 3));
    n = n + 3;
  }

  void zavrsi_minus() {
    for(auto x : zadnji_sloj)
      bridovi.push_back(par(x, n + 1));
    n = n + 1;
  }

  void ispis() {
    printf("%d %d\n", n, (int) bridovi.size());
    for(auto p : bridovi)
      printf("%d %d\n", p.X, p.Y);
  }

};

vector<int> odredi_binarni_zapis(llint t) {
  vector<int> ret;
  while(t > 0) {
    if(t & 1) ret.push_back(1);
    else ret.push_back(0);
    t /= 2;
  }
  reverse(ret.begin(), ret.end());
  return ret;
}

graf rijesi(llint t) {
  if(t == 0) {
    graf g(3, {par(1, 2), par(2, 3)});
    return g;
  }
  graf g;
  vector<int> binarno = odredi_binarni_zapis(abs(t));
  llint pref = 1;
  FOR(i, 1, (int) binarno.size()) {
    pref = g.puta_minus_dva(pref);
    if(binarno[i]) {
      if(pref < 0)
        pref = g.oduzmi_jedan(pref);
      else
        pref = g.dodaj_jedan(pref);
    }
  }
  assert(abs(t) == abs(pref));
  if(pref == t) g.zavrsi_isti();
  else g.zavrsi_minus();
  return g;
}

void pozovi(llint t) {
  graf g = rijesi(t);
  g.ispis();
}

int main() {
  llint t;
  cin >> t;
  pozovi(t);
  return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
20.0 / 20.0

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

Subtask #4
60.0 / 60.0

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