oj.uz

Submission #835277

# Submission time Handle Problem Language Result Execution time Memory
835277 2023-08-23T11:37:21 Z Pablo_No Mechanical Doll (IOI18_doll) C++17
30 / 100
 1000 ms 11396 KB 
#include "doll.h"

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#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(vector<int> rem)
{
  bool eq = true;
  for(int xx : rem) if(xx != rem[0])
      eq = false;
    
  if(eq)
  {
    //cerr << "*" << rem[0] << '\n';
    return rem[0];
  }
  ///

  vector<int> v1;
  vector<int> v2;

  for(int i = 0; i < rem.size(); i++)
  {
    if(i < rem.size()/2)
      v1.push_back(rem[i]);
    else
      v2.push_back(rem[i]);
  }

  int id = S.size();
  S.push_back({0, 0});

  int na = constr(v1);
  int nb = constr(v2);

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

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

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 19 ms 6328 KB Output is correct
3 Correct 15 ms 5180 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 3796 KB Output is correct
6 Correct 38 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 0 ms 212 KB Output is correct
2 Correct 19 ms 6328 KB Output is correct
3 Correct 15 ms 5180 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 3796 KB Output is correct
6 Correct 38 ms 7748 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Execution timed out 1076 ms 6080 KB Time limit exceeded
9 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 19 ms 6328 KB Output is correct
3 Correct 15 ms 5180 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 3796 KB Output is correct
6 Correct 38 ms 7748 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Execution timed out 1076 ms 6080 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 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 22 ms 6472 KB Output is correct
3 Correct 24 ms 10016 KB Output is correct
4 Correct 39 ms 11396 KB Output is correct

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 22 ms 6472 KB Output is correct
3 Correct 24 ms 10016 KB Output is correct
4 Correct 39 ms 11396 KB Output is correct
5 Execution timed out 1079 ms 8888 KB Time limit exceeded
6 Halted 0 ms 0 KB -