oj.uz

Submission #130362

# Submission time Handle Problem Language Result Execution time Memory
130362 2019-07-15T01:40:19 Z cjoa Mechanical Doll (IOI18_doll) C++11
85.5534 / 100
 244 ms 14580 KB 
#include "doll.h"
 
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cassert>
#include <cstdio>
 
using namespace std;
 
 
namespace TreeSol {
 
typedef vector<int> VI;
 
const int UNDEFINED = 999999;

struct Node {
   int L, R;
   int id;
   bool flipped, leaf;
   Node(int _L = -1, int _R = -1, int _id = UNDEFINED)
      : L(_L), R(_R), id(_id), flipped(false), leaf(false) {}
};
 
vector<Node> nodes;

void build_tree(int idx, int L, int R) {
   if (L == R) {
      nodes[idx] = Node(L, R);
      nodes[idx].leaf = true;
      return;
   }
   int mid = (L+R)/2;
   nodes[idx] = Node(L, R, -idx);
   build_tree(idx*2, L, mid);
   build_tree(idx*2+1, mid+1, R);
}
 
void assign_device_id(int id, int from, int idx = 1) {
   if (nodes[idx].L == nodes[idx].R) {
      if (nodes[idx].L >= from)
         nodes[idx].id = id;
      else {
         nodes[idx].id = -1;
         assign_device_id(id, from);
      }
      return;
   }
   nodes[idx].flipped = !nodes[idx].flipped;
   if (nodes[idx].flipped)
      assign_device_id(id, from, 2*idx);
   else
      assign_device_id(id, from, 2*idx+1);
}

void compress_tree(int idx = 1) {
    if (nodes[idx].L == nodes[idx].R)
       return;

    compress_tree(idx*2);
    compress_tree(idx*2 + 1);
    if (nodes[idx*2].leaf && nodes[idx*2+1].leaf && 
        nodes[idx*2].id == nodes[idx*2+1].id) {
        nodes[idx].leaf = true;
        nodes[idx].id = nodes[idx*2].id;
    }
}

void reassign_switch_ids(map<int,int>& reassigned_ids,
                         int& last_switch_id, int idx = 1) {
    int id = nodes[idx].id;
    if (id < 0) {
        if (reassigned_ids.count(id))
            nodes[idx].id = reassigned_ids[id];
        else {
            last_switch_id++;
            nodes[idx].id = reassigned_ids[id] = -last_switch_id;
        }
    }
    if (nodes[idx].leaf)
        return;
    if (nodes[idx].L == nodes[idx].R)
       return;
    reassign_switch_ids(reassigned_ids, last_switch_id, idx*2);
    reassign_switch_ids(reassigned_ids, last_switch_id, idx*2 + 1);
}


struct Switch {
   int x, y;
};
vector<Switch> switches;

void assign_switch_exits(int idx = 1) {
   if (nodes[idx].L < 0) return;
   if (nodes[idx].leaf) return;
   int id = nodes[idx].id;
   if (id < 0) {
      id = -(id+1);
      switches[ id ].x = nodes[idx*2  ].id;
      switches[ id ].y = nodes[idx*2+1].id;
   }
   assign_switch_exits(idx*2);
   assign_switch_exits(idx*2 + 1);
}


int build_circuit(int src, const VI& nxt) {
   int K = nxt.size();
   if (K == 1)
      return nxt[0];

   if (count(nxt.begin(), nxt.end(), nxt[0]) == K)
      return nxt[0];
 
   int nodes_last_level = 1;
   while (nodes_last_level < K)
      nodes_last_level *= 2;
 
   nodes = vector<Node>(2*nodes_last_level);

   build_tree(1, 0, nodes_last_level-1);
 
   int from = nodes_last_level - K;
   for (int dev_id : nxt)
      assign_device_id(dev_id, from);

   /*
   fprintf(stderr, "src: %d\n", src);
   fprintf(stderr, "nodes_last_level:%d  K:%d\n", nodes_last_level, K);
   */

   /*
   fprintf(stderr, "After assigned device ids\n");
   for (int idx = 1; idx < int(nodes.size()); ++idx) {
      Node x = nodes[idx];
      fprintf(stderr, "%3d  [%d,%d]  id:%d  leaf:%d\n", idx, x.L, x.R, x.id, x.leaf);
   }
   fprintf(stderr, "\n");
   */
 
   compress_tree();

   /*
   fprintf(stderr, "After compression\n");
   for (int idx = 1; idx < int(nodes.size()); ++idx) {
      Node x = nodes[idx];
      fprintf(stderr, "%3d  [%d,%d]  id:%d  leaf:%d\n", idx, x.L, x.R, x.id, x.leaf);
   }
   fprintf(stderr, "\n");
   */

   int last_switch_id = switches.size();
   map<int,int> reassigned_ids;
   reassign_switch_ids(reassigned_ids, last_switch_id);

   /*
   fprintf(stderr, "After reassignment\n");
   for (int idx = 1; idx < int(nodes.size()); ++idx) {
      Node x = nodes[idx];
      fprintf(stderr, "%3d  [%d,%d]  id:%d  leaf:%d\n", idx, x.L, x.R, x.id, x.leaf);
   }
   fprintf(stderr, "\n");
   */

   // fprintf(stderr, "last_switch_id:%d\n", last_switch_id);
   switches.resize( last_switch_id );

   assign_switch_exits();
   // fprintf(stderr, "END\n\n"); 

   return nodes[1].id;
}
 
}
 
void create_circuit(int M, std::vector<int> A) {
   int N = A.size();
 
   vector< vector<int> > nxt(M+1);
   for (int i = 1; i < N; ++i)
      nxt[ A[i-1] ].push_back( A[i] );
   nxt[ A.back() ].push_back(0);
 
   vector<int> C(M + 1);
   C[0] = A[0];
 
   for (int i = 1; i <= M; ++i) {
      if (nxt[i].empty()) continue;
      C[i] = TreeSol::build_circuit(i, nxt[i]);
   }
 
   int S = TreeSol::switches.size();
   vector<int> X(S), Y(S);
   for (int j = 0; j < S; ++j) {
      X[j] = TreeSol::switches[j].x;
      Y[j] = TreeSol::switches[j].y;
   // fprintf(stderr, "j:%d  x:%d  y:%d\n", j, X[j], Y[j]);
   }
   answer(C, X, Y);
 
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 33 ms 6308 KB Output is correct
3 Correct 26 ms 5068 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 3788 KB Output is correct
6 Correct 50 ms 7592 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 33 ms 6308 KB Output is correct
3 Correct 26 ms 5068 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 3788 KB Output is correct
6 Correct 50 ms 7592 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 86 ms 7660 KB Output is correct
9 Correct 73 ms 8848 KB Output is correct
10 Correct 135 ms 11560 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 2 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 33 ms 6308 KB Output is correct
3 Correct 26 ms 5068 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 3788 KB Output is correct
6 Correct 50 ms 7592 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 86 ms 7660 KB Output is correct
9 Correct 73 ms 8848 KB Output is correct
10 Correct 135 ms 11560 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 2 ms 204 KB Output is correct
14 Correct 142 ms 12988 KB Output is correct
15 Correct 74 ms 6460 KB Output is correct
16 Correct 111 ms 9868 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 2 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 160 ms 11816 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 95 ms 6056 KB Output is correct
3 Correct 178 ms 10128 KB Output is correct
4 Correct 216 ms 10964 KB Output is correct

Subtask #6
41.5533523496 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 95 ms 6056 KB Output is correct
3 Correct 178 ms 10128 KB Output is correct
4 Correct 216 ms 10964 KB Output is correct
5 Partially correct 144 ms 14580 KB Output is partially correct
6 Partially correct 178 ms 14368 KB Output is partially correct
7 Partially correct 149 ms 14496 KB Output is partially correct
8 Partially correct 149 ms 13568 KB Output is partially correct
9 Correct 160 ms 12592 KB Output is correct
10 Correct 244 ms 12472 KB Output is correct
11 Partially correct 161 ms 11532 KB Output is partially correct
12 Partially correct 98 ms 7740 KB Output is partially correct
13 Partially correct 89 ms 9512 KB Output is partially correct
14 Partially correct 93 ms 9556 KB Output is partially correct
15 Partially correct 104 ms 9704 KB Output is partially correct
16 Partially correct 5 ms 460 KB Output is partially correct
17 Partially correct 86 ms 7368 KB Output is partially correct
18 Partially correct 95 ms 7252 KB Output is partially correct
19 Partially correct 110 ms 7336 KB Output is partially correct
20 Partially correct 127 ms 11364 KB Output is partially correct
21 Partially correct 137 ms 11204 KB Output is partially correct
22 Partially correct 159 ms 10884 KB Output is partially correct