oj.uz

Submission #836737

# Submission time Handle Problem Language Result Execution time Memory
836737 2023-08-24T14:40:14 Z Johann Mechanical Doll (IOI18_doll) C++14
37 / 100
 77 ms 14880 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 + 1);
  A.push_back(0);
  for (int i = 0; i < sz(A); ++i)
    order[A[i]].push_back(A[(i + 1) % sz(A)]);

  int firstSwitch = newSwitch();

  for (int i = 0; i < sz(order); ++i)
    if (order[i].empty())
      C[i] = 0;
    else
      C[i] = firstSwitch;

  vi layer = {firstSwitch};
  while (sz(A) > 2 * sz(layer))
  {
    vi nlayer;
    // the order of these loops is important!
    for (int s : layer)
    {
      setSwitch(X, s, newSwitch());
      nlayer.push_back(getSwitch(X, s));
    }
    for (int s : layer)
    {
      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(A) - 1) ? A[idx++] : firstSwitch);
  for (int j = 0; j < sz(layer); ++j)
    setSwitch(Y, layer[j],
              ((idx < sz(A) - 1) || (j == sz(layer) - 1)) ? A[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 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Output is partially correct
2 Partially correct 51 ms 10400 KB Output is partially correct
3 Partially correct 50 ms 10448 KB Output is partially correct
4 Partially correct 61 ms 12220 KB Output is partially correct

Subtask #6
28.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Output is partially correct
2 Partially correct 51 ms 10400 KB Output is partially correct
3 Partially correct 50 ms 10448 KB Output is partially correct
4 Partially correct 61 ms 12220 KB Output is partially correct
5 Partially correct 77 ms 14880 KB Output is partially correct
6 Partially correct 74 ms 14200 KB Output is partially correct
7 Partially correct 70 ms 14340 KB Output is partially correct
8 Partially correct 68 ms 13728 KB Output is partially correct
9 Partially correct 50 ms 10320 KB Output is partially correct
10 Partially correct 61 ms 13236 KB Output is partially correct
11 Partially correct 57 ms 13256 KB Output is partially correct
12 Partially correct 51 ms 11416 KB Output is partially correct
13 Partially correct 58 ms 11836 KB Output is partially correct
14 Partially correct 61 ms 11924 KB Output is partially correct
15 Partially correct 66 ms 12064 KB Output is partially correct
16 Partially correct 2 ms 724 KB Output is partially correct
17 Correct 32 ms 8204 KB Output is correct
18 Partially correct 52 ms 10824 KB Output is partially correct
19 Partially correct 52 ms 10960 KB Output is partially correct
20 Partially correct 63 ms 12956 KB Output is partially correct
21 Partially correct 59 ms 13092 KB Output is partially correct
22 Partially correct 58 ms 12716 KB Output is partially correct