oj.uz

Submission #234406

# Submission time Handle Problem Language Result Execution time Memory
234406 2020-05-24T07:08:01 Z doowey Konstrukcija (COCI20_konstrukcija) C++14
110 / 110
 5 ms 384 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 100;
vector<int> T[N];
bool vis[N];
int dp[N][2];

void dfs(int u){
  vis[u]=true;
  for(auto x : T[u])
    if(!vis[x])dfs(x);
}

ll calc(int n, vector<pii> edg){
  dp[1][0]=1;
  for(auto x : edg)
    T[x.se].push_back(x.fi);
  for(int i = 2; i <= n; i ++ ){
    for(int j = 1; j <= n; j ++ )
      vis[j]=false;
    dfs(i);
    for(int j = 1 ; j < i ; j ++ ){
      if(!vis[j]) continue;
      dp[i][0]+=dp[j][1];
      dp[i][1]+=dp[j][0];
    }
  }
  return dp[n][0]-dp[n][1];
}

int main(){
  fastIO;
  ll k;
  cin >> k;
  if(k == 0){
    cout << "3 2\n"<< "1 2\n2 3\n";
    return 0;
  }
  if(k == 1){
    cout << "1 0\n";
    return 0;
  }
  ll go = abs(k);
  vector<int> di;
  di.push_back(1);
  vector<int> tt;
  int sig = 0;
  ll cur = -1;
  for(int i = 0 ; i <= 60 ; i ++ ){
    if((go&(1ll<<i)))
      sig=i;
  }
  for(int i = sig; i >= 0 ; i -- ){
    if(i < sig && (go&(1ll<<i))){
      di.push_back(2);
      cur *= -1ll;
      if(cur > 0){
        di.push_back(2);
        cur *= -1ll;
      }
      tt.push_back(di.size() - 1);
      cur -- ;
    }
    if(i > 0){
      di.push_back(3);
      cur *= -2ll;
    }
  }
  if(cur != k){
    di.push_back(2);
    cur *= -1;
  }
  di.push_back(1);
  int nn = tt.size();
  for(auto x : di)
    nn += x;
  int m = di.size();
  vector<int> p[m];
  p[m-1].push_back(nn);
  int c = 1;
  for(int i = 0 ; i + 1 < m ; i ++ ){
    for(int x = 0; x < di[i]; x ++ ){
      p[i].push_back(c);
      c++;
    }
  }
  vector<pii> sol;
  for(int i = 0 ; i < tt.size(); i ++ ){
    sol.push_back(mp(1, c));
    for(auto x : p[tt[i]])
      sol.push_back(mp(c, x));
    c ++ ;
  }
  for(int i = 0 ; i + 1 < m; i ++ ){
    for(auto x : p[i]){
      for(auto y : p[i + 1]){
        sol.push_back(mp(x,y));
      }
    }
  }
  cout << nn << " " << sol.size() << "\n";
  for(auto x : sol)
    cout << x.fi << " " << x.se << "\n";
  return 0;
}

Compilation message

konstrukcija.cpp: In function 'int main()':
konstrukcija.cpp:99:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < tt.size(); i ++ ){
                   ~~^~~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
20.0 / 20.0

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

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Correct.
2 Correct 5 ms 384 KB Correct.
3 Correct 5 ms 384 KB Correct.
4 Correct 5 ms 384 KB Correct.
5 Correct 5 ms 384 KB Correct.
6 Correct 5 ms 384 KB Correct.
7 Correct 4 ms 384 KB Correct.
8 Correct 5 ms 384 KB Correct.
9 Correct 5 ms 384 KB Correct.
10 Correct 5 ms 384 KB Correct.
11 Correct 4 ms 384 KB Correct.
12 Correct 5 ms 384 KB Correct.
13 Correct 5 ms 384 KB Correct.
14 Correct 5 ms 384 KB Correct.
15 Correct 5 ms 384 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 5 ms 384 KB Correct.
23 Correct 5 ms 384 KB Correct.
24 Correct 5 ms 384 KB Correct.
25 Correct 5 ms 384 KB Correct.
26 Correct 5 ms 384 KB Correct.
27 Correct 5 ms 384 KB Correct.