oj.uz

Submission #835297

# Submission time Handle Problem Language Result Execution time Memory
835297 2023-08-23T12:03:23 Z Pablo_No Mechanical Doll (IOI18_doll) C++17
85.5534 / 100
 96 ms 17000 KB 
#include "doll.h"
  
#include <vector>
#include <algorithm>
#include <iostream>
  
using namespace std;

vector<int> X;
vector<int> Y;
  
vector<int> prec[50];
  
vector<int> constrv(int dep)
{
  if(!prec[dep].empty())
    return prec[dep];
  
  vector<int> ans(1, 0);
  
  for(int d = 0; d < dep; d++)
  {
    vector<int> nans;
    for(int k = 0; k < (1 << d); k++)
    {
      nans.push_back(ans[k]);
      nans.push_back(ans[k]+(1 << d));
    }
    ans = nans;
  }
  
  return prec[dep] = ans;
}
  
int constr(const vector<int>& rem, int l, int r)
{
  bool eq = true;
  for(int i = l; i <= r; i++) if(rem[i] != rem[l])
      eq = false;
    
  if(eq)
  {
    //cerr << "*" << rem[0] << '\n';
    return rem[l];
  }
  ///
  
  int id = X.size();
  X.push_back(0);
  Y.push_back(0);
  
  int na = constr(rem, l, l+(r-l+1)/2-1);
  int nb = constr(rem, l+(r-l+1)/2, r);
  
  X[id] = na;
  Y[id] = nb;
  
  return -id-1;
}

const int N = 2e5+5;

vector<int> pos[N];
  
void create_circuit(int M, std::vector<int> A) {
  int N = A.size();
  vector<int> st(M+1, 0);
  
  pos[0].push_back(A[0]);
  
  for(int i = 0; i < N-1; i++)
  {
    pos[A[i]].push_back(A[i+1]);
  }
  
  pos[A[N-1]].push_back(0);
  
  for(int i = 1; i <= M; i++) if(!pos[i].empty())
  {
    if(pos[i].size() == 1)
    {
      st[i] = pos[i][0];
      continue;
    }
  
    int ni = pos[i].size();
    int log = __builtin_clz(1)-__builtin_clz((int)pos[i].size()-1)+1;
    int p2 = (1 << log);
  
    vector<int> m = constrv(log);
  
    /*for(auto x : m)
      cerr << x << ' ';
    cerr << '\n';*/
  
    vector<pair<int, int>> pm;
    for(int k = p2-ni; k < p2; k++)
    {
      pm.push_back({m[k], k});
      //cerr << m[k] << '-' << pos[i][k-(p2-ni)] << '\n';
    }
  
    vector<int> toc(p2, -X.size()-1);
  
    sort(pm.begin(), pm.end());
  
    for(int k = 0; k < pm.size(); k++)
    {
      auto [aa, bb] = pm[k];
      //cerr << aa << '+' << bb << '\n';
      toc[bb] = pos[i][k];
    }
  
    /*for(int xx : toc)
      cerr << xx << ' ';
    cerr << '\n';*/
  
    st[i] = constr(toc, 0, toc.size()-1);
  }
  
  st[0] = A[0];
  
  answer(st, X, Y);
}

Compilation message

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

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 19 ms 8740 KB Output is correct
3 Correct 17 ms 8340 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 9 ms 6100 KB Output is correct
6 Correct 23 ms 10068 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 19 ms 8740 KB Output is correct
3 Correct 17 ms 8340 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 9 ms 6100 KB Output is correct
6 Correct 23 ms 10068 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 42 ms 10392 KB Output is correct
9 Correct 37 ms 11908 KB Output is correct
10 Correct 63 ms 14856 KB Output is correct
11 Correct 2 ms 4996 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 2 ms 4948 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 19 ms 8740 KB Output is correct
3 Correct 17 ms 8340 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 9 ms 6100 KB Output is correct
6 Correct 23 ms 10068 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 42 ms 10392 KB Output is correct
9 Correct 37 ms 11908 KB Output is correct
10 Correct 63 ms 14856 KB Output is correct
11 Correct 2 ms 4996 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 2 ms 4948 KB Output is correct
14 Correct 76 ms 16108 KB Output is correct
15 Correct 40 ms 10664 KB Output is correct
16 Correct 60 ms 13708 KB Output is correct
17 Correct 2 ms 4948 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct
20 Correct 66 ms 15220 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 2 ms 4948 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 23 ms 9604 KB Output is correct
3 Correct 24 ms 12212 KB Output is correct
4 Correct 38 ms 13472 KB Output is correct

Subtask #6
41.5533523496 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 23 ms 9604 KB Output is correct
3 Correct 24 ms 12212 KB Output is correct
4 Correct 38 ms 13472 KB Output is correct
5 Partially correct 74 ms 15648 KB Output is partially correct
6 Partially correct 96 ms 16760 KB Output is partially correct
7 Partially correct 72 ms 16952 KB Output is partially correct
8 Partially correct 64 ms 16084 KB Output is partially correct
9 Correct 36 ms 11200 KB Output is correct
10 Correct 62 ms 17000 KB Output is correct
11 Partially correct 57 ms 14864 KB Output is partially correct
12 Partially correct 37 ms 11420 KB Output is partially correct
13 Partially correct 50 ms 12612 KB Output is partially correct
14 Partially correct 47 ms 12808 KB Output is partially correct
15 Partially correct 49 ms 12840 KB Output is partially correct
16 Partially correct 4 ms 5204 KB Output is partially correct
17 Partially correct 41 ms 11168 KB Output is partially correct
18 Partially correct 43 ms 11920 KB Output is partially correct
19 Partially correct 40 ms 11164 KB Output is partially correct
20 Partially correct 56 ms 14412 KB Output is partially correct
21 Partially correct 61 ms 14512 KB Output is partially correct
22 Partially correct 58 ms 14140 KB Output is partially correct