oj.uz

Submission #836321

# Submission time Handle Problem Language Result Execution time Memory
836321 2023-08-24T10:09:57 Z Johann Mechanical Doll (IOI18_doll) C++14
15 / 100
 73 ms 14700 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)]);

  for (int i = 0; i < sz(order); ++i)
  {
    if (order[i].empty())
      C[i] = 0;
    else if (sz(order[i]) == 1)
      C[i] = order[i][0];
    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
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 19 ms 6736 KB Output is correct
3 Correct 22 ms 5600 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 11 ms 3796 KB Output is correct
6 Correct 23 ms 8396 KB Output is correct
7 Correct 1 ms 336 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 19 ms 6736 KB Output is correct
3 Correct 22 ms 5600 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 11 ms 3796 KB Output is correct
6 Correct 23 ms 8396 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 32 ms 8136 KB Output is correct
9 Correct 34 ms 9552 KB Output is correct
10 Correct 50 ms 12732 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 19 ms 6736 KB Output is correct
3 Correct 22 ms 5600 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 11 ms 3796 KB Output is correct
6 Correct 23 ms 8396 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 32 ms 8136 KB Output is correct
9 Correct 34 ms 9552 KB Output is correct
10 Correct 50 ms 12732 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 61 ms 12936 KB Output is correct
15 Incorrect 33 ms 6972 KB wrong motion
16 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 224 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Output is partially correct
2 Correct 28 ms 7364 KB Output is correct
3 Partially correct 47 ms 9052 KB Output is partially correct
4 Partially correct 51 ms 10304 KB Output is partially correct

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Output is partially correct
2 Correct 28 ms 7364 KB Output is correct
3 Partially correct 47 ms 9052 KB Output is partially correct
4 Partially correct 51 ms 10304 KB Output is partially correct
5 Incorrect 73 ms 14700 KB wrong motion
6 Halted 0 ms 0 KB -