oj.uz

Submission #836316

# Submission time Handle Problem Language Result Execution time Memory
836316 2023-08-24T10:06:48 Z Johann Mechanical Doll (IOI18_doll) C++14
0 / 100
 55 ms 468 KB 
#include "doll.h"
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

int switches;
vector<int> X, Y;
int newSwitch()
{
  X.push_back(0), Y.push_back(0);
  return --switches;
}
void setSwitch(vector<int> &XY, int switchnum, int dest)
{
  XY[-switchnum - 1] = dest;
}
int getSwitch(vector<int> &XY, int i) { return XY[-i - 1]; }

void create_circuit(int M, std::vector<int> A)
{
  int N = A.size();
  switches = 0;

  vi C(M + 1);

  vvi order(M);
  A.push_back(0);
  for (int i = 0; i < sz(A); ++i)
    order[A[i]].push_back(A[(i + 1) % sz(A)]);

  for (int i = 0; i < M; ++i)
  {
    if (order[i].empty())
      C[i] = 0;
    else if (sz(order[i]) == 1)
      C[i] = order[i].front();
    else
    {
      int firstSwitch = newSwitch();
      C[i] = firstSwitch;
      vi layer = {firstSwitch};
      while (sz(order[i]) > 2 * sz(layer))
      {
        vi nlayer;
        for (int s : layer)
        {
          setSwitch(X, s, newSwitch());
          nlayer.push_back(getSwitch(X, s));
          setSwitch(Y, s, newSwitch());
          nlayer.push_back(getSwitch(Y, s));
        }
        swap(layer, nlayer);
      }

      int idx = 0;
      for (int j = 0; j < sz(layer); ++j)
      {
        setSwitch(X, layer[j],
                  (idx < sz(order[i]) - 1) ? order[i][idx++] : firstSwitch);
        setSwitch(Y, layer[j],
                  (idx < sz(order[i]) - 1 || j == sz(layer) - 1) ? order[i][idx++] : firstSwitch);
      }
    }
  }

  answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:29:7: warning: unused variable 'N' [-Wunused-variable]
   29 |   int N = A.size();
      |       ^

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 55 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Runtime error 55 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -