oj.uz

Submission #835295

# Submission time Handle Problem Language Result Execution time Memory
835295 2023-08-23T12:00:37 Z Pablo_No Mechanical Doll (IOI18_doll) C++17
30 / 100
 1000 ms 13508 KB 
#include "doll.h"
  
#include <vector>
#include <algorithm>
#include <iostream>
  
using namespace std;

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;
}

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, -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:104: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]
  104 |     for(int k = 0; k < pm.size(); k++)
      |                    ~~^~~~~~~~~~~
doll.cpp:126: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]
  126 |   for(int i = 0; i < S.size(); i++)
      |                  ~~^~~~~~~~~~
doll.cpp:123:11: warning: unused variable 'xx' [-Wunused-variable]
  123 |   for(int xx : st)
      |           ^~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 22 ms 8660 KB Output is correct
3 Correct 15 ms 8276 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 11 ms 6100 KB Output is correct
6 Correct 27 ms 10068 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 22 ms 8660 KB Output is correct
3 Correct 15 ms 8276 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 11 ms 6100 KB Output is correct
6 Correct 27 ms 10068 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Execution timed out 1043 ms 9300 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 22 ms 8660 KB Output is correct
3 Correct 15 ms 8276 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 11 ms 6100 KB Output is correct
6 Correct 27 ms 10068 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Execution timed out 1043 ms 9300 KB Time limit exceeded
9 Halted 0 ms 0 KB -

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 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 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 3 ms 4948 KB Output is correct
2 Correct 25 ms 9544 KB Output is correct
3 Correct 23 ms 12100 KB Output is correct
4 Correct 38 ms 13508 KB Output is correct

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 25 ms 9544 KB Output is correct
3 Correct 23 ms 12100 KB Output is correct
4 Correct 38 ms 13508 KB Output is correct
5 Execution timed out 1054 ms 12620 KB Time limit exceeded
6 Halted 0 ms 0 KB -