oj.uz

Submission #713761

# Submission time Handle Problem Language Result Execution time Memory
713761 2023-03-23T02:39:42 Z LittleOrange Mechanical Doll (IOI18_doll) C++17
37 / 100
 119 ms 14516 KB 
#include "doll.h"
#include<bits/stdc++.h>
using namespace std;
using ll = int;
 
void create_circuit(int M, std::vector<int> A) {
  int N = A.size();
  std::vector<int> C(M + 1,0);
  C[0] = A[0];
  if (N == 1){
    for (int i = 1; i <= M; ++i) C[i] = 0;
    vector<int> X,Y; 
    answer(C, X, Y);
    return;
  }else if (N==16){
    
  ll GN = 1<<(__lg(N-1)+1);
  while (A.size()<GN) A.push_back(-1);
  A.push_back(0);
  vector<int> X(GN-1),Y(GN-1);
  ll it = 0;
  function<ll(ll,ll,ll)> dfs;
  dfs = [&](ll cnt, ll st, ll lv){
    if (cnt==1){
        return A[st+1];
    }
    ll i = it++;
    X[i] = dfs(cnt-cnt/2,st,lv+1);
    Y[i] = dfs(cnt/2,st+(1<<lv),lv+1);
    return -1-i;
  };
  dfs(GN,0,0);
  answer(C, X, Y);
  }
  A.push_back(0);
  vector<vector<ll>> nxt(M);
  for(ll i = 0;i<N;i++){
    nxt[A[i]-1].push_back(A[i+1]);
  }
  for(auto &o : nxt){
    if (o.size()>2) {
        ll old = o.back();
        o.pop_back();
        o.resize(1<<(__lg(o.size())+1),-1);
        o.back() = old;
    }
  }
  vector<int> X,Y;
  ll it = 0;
  vector<ll> CUR;
  ll root;
  function<ll(ll,ll,ll)> dfs;
  dfs = [&](ll cnt, ll st, ll lv){
    //cerr << "dfs " << cnt << " " << st << " " << lv << " " << CUR[st] << "\n";
    if (cnt==1){
        return CUR[st]==-1?root:CUR[st];
    }
    ll i = it++;
    X.emplace_back();
    Y.emplace_back();
    X[i] = dfs(cnt-cnt/2,st,lv+1);
    Y[i] = dfs(cnt/2,st+(1<<lv),lv+1);
    return -1-i;
  };
  for(ll i = 0;i<M;i++){
    CUR = nxt[i];
    if (CUR.size()>1){
        C[i+1] = root = -1-it;
        dfs(CUR.size(),0,0);
    }else if(CUR.size()==1){
        C[i+1] = CUR[0];
    }
  }
  for(ll i = 0;i<N;i++) {
    //cerr << "nxt " << i << ":";
    //for(ll j : nxt[i]) cerr << " " << j;
    //cerr << "\n";
  }
  answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:18:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   18 |   while (A.size()<GN) A.push_back(-1);
      |          ~~~~~~~~^~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 25 ms 6352 KB Output is correct
3 Correct 21 ms 5084 KB Output is correct
4 Incorrect 1 ms 212 KB Wrong Answer: answered not exactly once
5 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 25 ms 6352 KB Output is correct
3 Correct 21 ms 5084 KB Output is correct
4 Incorrect 1 ms 212 KB Wrong Answer: answered not exactly once
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 25 ms 6352 KB Output is correct
3 Correct 21 ms 5084 KB Output is correct
4 Incorrect 1 ms 212 KB Wrong Answer: answered not exactly once
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Wrong Answer: answered not exactly once
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Output is partially correct
2 Correct 43 ms 6828 KB Output is correct
3 Partially correct 72 ms 9604 KB Output is partially correct
4 Partially correct 77 ms 10428 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Output is partially correct
2 Correct 43 ms 6828 KB Output is correct
3 Partially correct 72 ms 9604 KB Output is partially correct
4 Partially correct 77 ms 10428 KB Output is partially correct
5 Partially correct 100 ms 12072 KB Output is partially correct
6 Partially correct 107 ms 12632 KB Output is partially correct
7 Partially correct 93 ms 12464 KB Output is partially correct
8 Partially correct 119 ms 12816 KB Output is partially correct
9 Partially correct 60 ms 9884 KB Output is partially correct
10 Partially correct 99 ms 14516 KB Output is partially correct
11 Partially correct 100 ms 14288 KB Output is partially correct
12 Partially correct 65 ms 9360 KB Output is partially correct
13 Partially correct 81 ms 8280 KB Output is partially correct
14 Partially correct 64 ms 8128 KB Output is partially correct
15 Partially correct 61 ms 8024 KB Output is partially correct
16 Partially correct 2 ms 468 KB Output is partially correct
17 Partially correct 59 ms 7140 KB Output is partially correct
18 Partially correct 54 ms 7220 KB Output is partially correct
19 Partially correct 55 ms 7528 KB Output is partially correct
20 Partially correct 81 ms 9892 KB Output is partially correct
21 Partially correct 86 ms 11704 KB Output is partially correct
22 Partially correct 73 ms 9256 KB Output is partially correct