oj.uz

Submission #767151

# Submission time Handle Problem Language Result Execution time Memory
767151 2023-06-26T12:48:40 Z canadavid1 Mechanical Doll (IOI18_doll) C++14
100 / 100
 168 ms 33140 KB 
#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

struct Switch
{
  bool state;
  Switch *l,*r;
  int lv=-1,rv=-1;
  int num=0;
};

Switch *create_tree(int li,int ri)
{
  Switch* a = new Switch();
  a->state = false;
  if(ri-li > 2)
  {
    int m = (li+ri)>>1;
    a->l = create_tree(li,m);
    a->r = create_tree(m,ri);
  }
  else
  {
    a->l = nullptr;
    a->r = nullptr;
  }
  return a;
}

int& traverse(Switch* root)
{
  if(root->state)
  {
    root->state = false;
    if(root->r) return traverse(root->r);
    return root->rv;
  }
  else
  {
    root->state = true;
    if(root->l) return traverse(root->l);
    return root->lv;
  }
}

void prune(Switch *root,int b, int l,int r,Switch *here=nullptr)
{
  if(here==nullptr) here = root;
  if(l==b) return;
  
  int m = (l+r)/2;
  if (m <= b)
  {
    here->l = root;
    if(m==b) return;
    prune(root,b,m,r,here->r);
  }
  else prune(root,b,l,m,here->l);
}
vector<Switch*> switches;
int enumerate(Switch *here)
{
  static int i = 0;
  if(here == nullptr || here->num != 0) return -i;
  switches.push_back(here);
  here->num = --i;
  enumerate(here->l);
  enumerate(here->r);
  return -i;
}



void assign(Switch *here,vector<int>& X, vector<int>& Y)
{
  static set<Switch*> seen;
  if(seen.count(here)) return;
  seen.insert(here);
  if(!here) return;
  if(!here->num) return;
  if(here->l)
  {
    X[-here->num-1] = here->l->num;
  }
  else
  {
    X[-here->num-1] = here->lv;
  }
  if(here->r)
    Y[-here->num-1] = here->r->num;
  else
    Y[-here->num-1] = here->rv;
  
  assign(here->l,X,Y);
  assign(here->r,X,Y);
}
Switch* root;
void printTree(Switch* here,string prev = "", string out = "└─",string follow = "  ")
{
  return;
  if(here==nullptr) {cout << prev << out << "\n"; return;}
  cout << prev << out << here->num << " " << here->lv << " " << here->rv << " " << here->state << "\n";
  if(here->l == root)
    cout << prev << follow << "├─root\n";
  else if(here->l)
    printTree(here->l,prev+follow,"├─","│ ");
  if(here->r == root)
    cout << prev << follow << "└─root\n";
  else if(here->r)
    printTree(here->r,prev+follow,"└─","  ");

}
void set_neg2_root(Switch* here, Switch* root)
{
  if (here->lv==-2) here->l = root;
  else if (here->l!=root && here->l) set_neg2_root(here->l,root);
  if (here->rv==-2) here->r = root;
  else if (here->r!=root && here->r) set_neg2_root(here->r,root);
}


int log2(int a)
{
  int i = 0;
  for(;(1<<i)<a;i++);
  return i;
}

void create_circuit(int M, std::vector<int> A) {
  int N = A.size();
  int Nru = 1 << (log2(N+1));
  A.push_back(0);
  
  root = create_tree(0,Nru);
  printTree(root);
  prune(root,Nru-N-1,0,Nru);
  printTree(root);
  int num_switches = enumerate(root);
  printTree(root);
  vector<int> C(M+1),X(num_switches),Y(num_switches);
  for(auto i : A) traverse(root) = i;
  set_neg2_root(root,root);
  printTree(root);
  for(auto&& i : C) i = -1;
  assign(root,X,Y);  
  answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 53 ms 14140 KB Output is correct
3 Correct 50 ms 13540 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1492 KB Output is correct
6 Correct 74 ms 17344 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 53 ms 14140 KB Output is correct
3 Correct 50 ms 13540 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1492 KB Output is correct
6 Correct 74 ms 17344 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 104 ms 25956 KB Output is correct
9 Correct 104 ms 26556 KB Output is correct
10 Correct 160 ms 33140 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 53 ms 14140 KB Output is correct
3 Correct 50 ms 13540 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1492 KB Output is correct
6 Correct 74 ms 17344 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 104 ms 25956 KB Output is correct
9 Correct 104 ms 26556 KB Output is correct
10 Correct 160 ms 33140 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 150 ms 32712 KB Output is correct
15 Correct 98 ms 25504 KB Output is correct
16 Correct 156 ms 32344 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 168 ms 32788 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 106 ms 24496 KB Output is correct
3 Correct 95 ms 24520 KB Output is correct
4 Correct 143 ms 31028 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 106 ms 24496 KB Output is correct
3 Correct 95 ms 24520 KB Output is correct
4 Correct 143 ms 31028 KB Output is correct
5 Correct 148 ms 32164 KB Output is correct
6 Correct 147 ms 31896 KB Output is correct
7 Correct 150 ms 32056 KB Output is correct
8 Correct 149 ms 31676 KB Output is correct
9 Correct 96 ms 24584 KB Output is correct
10 Correct 150 ms 31632 KB Output is correct
11 Correct 145 ms 31260 KB Output is correct
12 Correct 106 ms 24816 KB Output is correct
13 Correct 98 ms 25212 KB Output is correct
14 Correct 100 ms 25248 KB Output is correct
15 Correct 117 ms 25400 KB Output is correct
16 Correct 3 ms 980 KB Output is correct
17 Correct 87 ms 18596 KB Output is correct
18 Correct 100 ms 24800 KB Output is correct
19 Correct 98 ms 24764 KB Output is correct
20 Correct 144 ms 31516 KB Output is correct
21 Correct 144 ms 31268 KB Output is correct
22 Correct 146 ms 31284 KB Output is correct