oj.uz

Submission #592963

# Submission time Handle Problem Language Result Execution time Memory
592963 2022-07-09T23:53:20 Z farhan132 Mechanical Doll (IOI18_doll) C++17
100 / 100
 298 ms 68740 KB 
#include "doll.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef int ll;
typedef pair<ll , ll> ii;
 
#define ff first
#define ss second
#define pb push_back

const ll N = 1e6 + 5;
vector < ll > v[N];
vector < ll > g[N];
ll S = 0;
ll col[N];
vector < ll > child;
vector < ll > X,Y;

void setX(ll i, ll x){
  X[abs(i) - 1] = x;
  return;
}
void setY(ll i, ll y){
  Y[abs(i) - 1] = y;
  return;
}
ll tot = 0;
ll _n;

ll breakdown(ll sz){
  if(sz == 2){
    S--;
    X.pb(0); Y.pb(0);
    tot += 2;
    return S;
  } 
  ll node = S - 1; S--; X.pb(0); Y.pb(0);
  ll n1 = breakdown(sz/2);
  g[-node].pb(-n1);
  setY(node, n1);
 // cout << node << ' ' << n1 << '\n'; 
  if(tot >= _n){
    setX(node, -1);
    return node;
  }
  ll n2 = breakdown(sz/2);
  g[-node].pb(-n2);
  setX(node, n2);
   //cout << node << ' ' << n2 << '\n'; 
  return node;
}
void go(ll node, ll sz){
  if(g[-node].size() == 0){
    child.pb(node); col[-node] ^= 1;
    return;
  }
  
  if(!col[-node]){
    col[-node] ^= 1;
    if(g[-node].size() == 2) go(-g[-node][1], sz/2);
    else go(-1, 0);
    
  }else{
   col[-node] ^= 1;
   go(-g[-node][0], sz/2);
   
  }

  
  return;
}

void create_circuit(int M, std::vector<int> A) {
  memset(col, 0, sizeof(col));
  ll n = A.size();
  A.pb(0);
  for(ll i = 0; i < n; i++){
    v[A[i]].pb(A[i + 1]);
  }
  ll m = M;
  vector < ll > C(m + 1); C[0] = A[0];

  vector < ll > all;
  ll mx = 0;

  for(ll i = 1; i <= m; i++){
    mx = max(mx, (ll)v[i].size());
    if(v[i].size() == 0){
      C[i] = 0;
      continue;
    }
    if(v[i].size() == 1){
      C[i] = v[i][0];
      continue;
    }
    C[i] = -1;
  }
  for(ll i = 0; i < n; i++){
    if(C[A[i]] == -1){
      all.pb(A[i + 1]);
    }
  }

  if(all.size()){
    _n = all.size();
    ll two = 1; ll d = 1;
    while(two * 2 < all.size()) two *= 2, d++;
    two *= 2;
    child.clear(); tot = 0;
    ll root = breakdown(two);
    memset(col, 0, sizeof(col));
    while(tot--) go(root, two);
    ll rem = child.size();
    memset(col, 0, sizeof(col));

    ll cur = 0;
    for(ll j = 0; j < child.size(); j++){
      if(rem > all.size()){
        if(col[-child[j]]) setY(child[j], root);
        else setX(child[j], root);
      }else{
        if(col[-child[j]]) setY(child[j], all[cur]);
        else setX(child[j], all[cur]);
        //cout << cur << ' ' << all[cur] << '\n';
        cur++;
      }
      col[-child[j]] ^= 1;
      rem--;
    }
  }
  #ifdef LOCAL
    for(ll i = 0; i <= m; i++){
      cout << C[i] << ' ';
    }
    cout << '\n';
    for(ll i = 0; i < X.size(); i++){
      cout << -(i + 1) << ' ' << X[i] << ' ' << Y[i] << '\n';
    }
  #endif
  answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:109:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     while(two * 2 < all.size()) two *= 2, d++;
      |           ~~~~~~~~^~~~~~~~~~~~
doll.cpp:119:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |     for(ll j = 0; j < child.size(); j++){
      |                   ~~^~~~~~~~~~~~~~
doll.cpp:120:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |       if(rem > all.size()){
      |          ~~~~^~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 51156 KB Output is correct
2 Correct 46 ms 54912 KB Output is correct
3 Correct 44 ms 54684 KB Output is correct
4 Correct 22 ms 51044 KB Output is correct
5 Correct 31 ms 52308 KB Output is correct
6 Correct 52 ms 56360 KB Output is correct
7 Correct 28 ms 51160 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 51156 KB Output is correct
2 Correct 46 ms 54912 KB Output is correct
3 Correct 44 ms 54684 KB Output is correct
4 Correct 22 ms 51044 KB Output is correct
5 Correct 31 ms 52308 KB Output is correct
6 Correct 52 ms 56360 KB Output is correct
7 Correct 28 ms 51160 KB Output is correct
8 Correct 132 ms 62752 KB Output is correct
9 Correct 123 ms 61456 KB Output is correct
10 Correct 269 ms 68740 KB Output is correct
11 Correct 26 ms 51116 KB Output is correct
12 Correct 31 ms 51148 KB Output is correct
13 Correct 27 ms 51148 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 51156 KB Output is correct
2 Correct 46 ms 54912 KB Output is correct
3 Correct 44 ms 54684 KB Output is correct
4 Correct 22 ms 51044 KB Output is correct
5 Correct 31 ms 52308 KB Output is correct
6 Correct 52 ms 56360 KB Output is correct
7 Correct 28 ms 51160 KB Output is correct
8 Correct 132 ms 62752 KB Output is correct
9 Correct 123 ms 61456 KB Output is correct
10 Correct 269 ms 68740 KB Output is correct
11 Correct 26 ms 51116 KB Output is correct
12 Correct 31 ms 51148 KB Output is correct
13 Correct 27 ms 51148 KB Output is correct
14 Correct 278 ms 67096 KB Output is correct
15 Correct 181 ms 61636 KB Output is correct
16 Correct 244 ms 66380 KB Output is correct
17 Correct 25 ms 51148 KB Output is correct
18 Correct 29 ms 51068 KB Output is correct
19 Correct 25 ms 51176 KB Output is correct
20 Correct 255 ms 67296 KB Output is correct
21 Correct 29 ms 51140 KB Output is correct
22 Correct 24 ms 51156 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 51156 KB Output is correct
2 Correct 28 ms 51172 KB Output is correct
3 Correct 25 ms 51172 KB Output is correct
4 Correct 25 ms 51156 KB Output is correct
5 Correct 28 ms 51060 KB Output is correct
6 Correct 24 ms 51156 KB Output is correct
7 Correct 25 ms 51148 KB Output is correct
8 Correct 25 ms 51156 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 51064 KB Output is correct
2 Correct 146 ms 60932 KB Output is correct
3 Correct 123 ms 60432 KB Output is correct
4 Correct 240 ms 64060 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 51064 KB Output is correct
2 Correct 146 ms 60932 KB Output is correct
3 Correct 123 ms 60432 KB Output is correct
4 Correct 240 ms 64060 KB Output is correct
5 Correct 239 ms 66664 KB Output is correct
6 Correct 276 ms 66268 KB Output is correct
7 Correct 235 ms 66420 KB Output is correct
8 Correct 298 ms 65872 KB Output is correct
9 Correct 131 ms 60432 KB Output is correct
10 Correct 261 ms 65156 KB Output is correct
11 Correct 226 ms 65324 KB Output is correct
12 Correct 145 ms 61212 KB Output is correct
13 Correct 149 ms 62148 KB Output is correct
14 Correct 139 ms 61812 KB Output is correct
15 Correct 140 ms 61880 KB Output is correct
16 Correct 27 ms 51428 KB Output is correct
17 Correct 171 ms 61468 KB Output is correct
18 Correct 120 ms 61380 KB Output is correct
19 Correct 144 ms 60992 KB Output is correct
20 Correct 225 ms 65204 KB Output is correct
21 Correct 246 ms 65088 KB Output is correct
22 Correct 223 ms 64796 KB Output is correct