Submission #88319

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
88319	2018-12-05T09:41:38 Z	memikakizaki	Mechanical Doll (IOI18_doll)	C++14	6 / 100	126 ms	14068 KB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5+1;

int n, m;
vector<int> a;
vector<vector<int> > ls;
vector<int> C, X, Y;

int nodes;
int l[N], r[N];
bool state[N];

void gen_adj(int root, int targ_sz) {
  l[root] = r[root] = -1;
  if(targ_sz / 2 >= 2) {
    l[root] = ++nodes;
    gen_adj(l[root], targ_sz / 2);
  }
  if(targ_sz - targ_sz / 2 >= 2) {
    r[root] = ++nodes;
    gen_adj(r[root], targ_sz - targ_sz / 2);
  }
}

void traverse(int root, vector<pair<int,int> > &ord) {
  // cout << root << ' ' << l[root] << ' ' << r[root] << endl;
  if(state[root]) {
    if(r[root] != -1) traverse(r[root], ord);
    else ord.emplace_back(root, 1);
  } else {
    if(l[root] != -1) traverse(l[root], ord);
    else ord.emplace_back(root, 0);
  }
  state[root] ^= 1;
}

pair<int, vector<pair<int,int> > > make_tree(int targ_sz) {
  int root = ++nodes;
  gen_adj(root, targ_sz);
  vector<pair<int,int> > ord;
  // cout << "targ_sz " << targ_sz << endl;
  for(int i = 1; i <= targ_sz; i++) traverse(root, ord);
  // cout << endl;
  // for(auto p: ord) cout << p.first << ' ' << p.second << endl;
  // cout << endl;
  X.resize(nodes);
  Y.resize(nodes);
  return make_pair(root, ord);
}

void create_circuit(int _m, std::vector<int> _a) {
  m = _m, n = _a.size();
  a = _a;
  ls.resize(m+1);
  C.resize(m+1);

  a.insert(a.begin(), 0);
  a.push_back(0);
  for(int i = 0; i <= n; i++) ls[a[i]].push_back(a[i+1]);
  for(int i = 0; i <= m; i++) {
    if(!ls[i].size()) C[i] = 1;
    else if(ls[i].size() == 1) C[i] = ls[i][0];
    else {
      int root;
      vector<pair<int,int> > ord;
      tie(root, ord) = make_tree(ls[i].size());
      C[i] = -root;
      assert(ord.size() == ls[i].size());
      for(int j = 0; j < ord.size(); j++) {
        int idx, tp;
        tie(idx, tp) = ord[j];
        if(tp == 0) X[idx-1] = ls[i][j];
        else Y[idx-1] = ls[i][j];
      }
    }
  }
  // for(int i = 0; i <= m; i++) cout << i << ' ' << C[i] << endl;
  // for(int i = 0; i < X.size(); i++) cout << X[i] <<' ' << Y[i] << endl;
  answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:71:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |       for(int j = 0; j < ord.size(); j++) {
      |                      ~~^~~~~~~~~~~~

Subtask #1
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	33 ms	6592 KB	Output is correct
3	Correct	31 ms	5528 KB	Output is correct
4	Correct	2 ms	204 KB	Output is correct
5	Correct	15 ms	3788 KB	Output is correct
6	Correct	44 ms	8304 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	1 ms	204 KB	Output is correct
2	Correct	33 ms	6592 KB	Output is correct
3	Correct	31 ms	5528 KB	Output is correct
4	Correct	2 ms	204 KB	Output is correct
5	Correct	15 ms	3788 KB	Output is correct
6	Correct	44 ms	8304 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	85 ms	9004 KB	Output is correct
9	Correct	77 ms	10000 KB	Output is correct
10	Correct	126 ms	14068 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct

Subtask #3
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	33 ms	6592 KB	Output is correct
3	Correct	31 ms	5528 KB	Output is correct
4	Correct	2 ms	204 KB	Output is correct
5	Correct	15 ms	3788 KB	Output is correct
6	Correct	44 ms	8304 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	85 ms	9004 KB	Output is correct
9	Correct	77 ms	10000 KB	Output is correct
10	Correct	126 ms	14068 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Incorrect	120 ms	12096 KB	wrong motion
15	Halted	0 ms	0 KB	-