oj.uz

Submission #835293

# Submission time Handle Problem Language Result Execution time Memory
835293 2023-08-23T11:56:26 Z Pablo_No Mechanical Doll (IOI18_doll) C++17
30 / 100
 1000 ms 8908 KB 
#include "doll.h"
  
#include <vector>
#include <algorithm>
#include <iostream>
  
using namespace std;
  
vector<int> st;
vector<pair<int, int>> S;
  
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 = S.size();
  S.push_back({0, 0});
  
  int na = constr(rem, l, l+(r-l+1)/2-1);
  int nb = constr(rem, l+(r-l+1)/2, r);
  
  S[id] = {na, nb};
  
  return -id-1;
}
  
void create_circuit(int M, std::vector<int> A) {
  int N = A.size();
  st.assign(M+1, 0);
  
  vector<vector<int>> pos(M+1);
  
  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, -S.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];
  
  vector<int> X(S.size());
  vector<int> Y(S.size());
  
  for(int xx : st)
    //cerr << xx << '\n';
  
  for(int i = 0; i < S.size(); i++)
  {
    X[i] = S[i].first;
    Y[i] = S[i].second;
    //cerr << X[i] << ' ' << Y[i] << '\n';
  }
  
  answer(st, X, Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:103: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]
  103 |     for(int k = 0; k < pm.size(); k++)
      |                    ~~^~~~~~~~~~~
doll.cpp:125:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |   for(int i = 0; i < S.size(); i++)
      |                  ~~^~~~~~~~~~
doll.cpp:122:11: warning: unused variable 'xx' [-Wunused-variable]
  122 |   for(int xx : st)
      |           ^~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 19 ms 6356 KB Output is correct
3 Correct 16 ms 5160 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 9 ms 3796 KB Output is correct
6 Correct 23 ms 7748 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 19 ms 6356 KB Output is correct
3 Correct 16 ms 5160 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 9 ms 3796 KB Output is correct
6 Correct 23 ms 7748 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Execution timed out 1069 ms 6196 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 19 ms 6356 KB Output is correct
3 Correct 16 ms 5160 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 9 ms 3796 KB Output is correct
6 Correct 23 ms 7748 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Execution timed out 1069 ms 6196 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 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 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 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 20 ms 4884 KB Output is correct
3 Correct 21 ms 7516 KB Output is correct
4 Correct 36 ms 8748 KB Output is correct

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 20 ms 4884 KB Output is correct
3 Correct 21 ms 7516 KB Output is correct
4 Correct 36 ms 8748 KB Output is correct
5 Execution timed out 1090 ms 8908 KB Time limit exceeded
6 Halted 0 ms 0 KB -