oj.uz

Submission #401312

# Submission time Handle Problem Language Result Execution time Memory
401312 2021-05-09T20:05:34 Z idk321 Mechanical Doll (IOI18_doll) C++11
47 / 100
 415 ms 40300 KB 
#include "doll.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int m, n;

vector<int> a;
vector<int> c;
vector<int> x;
vector<int> y;

vector<array<int, 2>> sAt;
int used;

int N;

vector<bool> endNode;
void solve(int ca, int cb, int node)
{

    if (ca == cb)
    {


        endNode[node] = true;
        return;
    }

    int mid = (ca + cb) / 2;
    array<int, 2> cur = {-node * 2, -node * 2 - 1};
    sAt[node] = cur;
    solve(ca, mid, node * 2);
    solve(mid + 1, cb, node * 2+  1);
}


void create_circuit(int M, std::vector<int> A) {
    m = M;
    a = A;
  n = A.size();

  std::vector<int> C(M + 1);
  C[0] = -1;

    N = 1;
    while (N < (n + 1) / 2)
    {
        N *= 2;
    }

    endNode.resize(4 * N);
    sAt.resize(4 * N);
  c = C;
  for (int i = 1; i <= m; i++) c[i] = -1;
    c[0] = a[0];

  used = 1;
    solve(1, N, 1);

   int cur = 1;
   int endNodeNum = 1;
   vector<int> switched(4 * N);
   while (true)
   {
        if (endNode[cur])
        {
            if (endNodeNum == N * 2)
            {
                sAt[cur][1] = 0;
            } else
            {
                if (used < n)
                {
                    sAt[cur][switched[cur]] = a[used];
                    used++;
                    switched[cur] = (switched[cur] + 1) % 2;
                } else
                {
                    sAt[cur][switched[cur]] = -1;
                    switched[cur] = (switched[cur] + 1) % 2;
                }
            }

            if (endNodeNum == N * 2) break;
            cur = 1;
            endNodeNum++;
        } else
        {
            int next = sAt[cur][switched[cur]] * (-1);
            switched[cur] = (switched[cur] + 1) % 2;
            cur = next;
        }
   }


  vector<int> x;
  vector<int> y;

  map<int, int> turnTo;
  set<int> nums;
  nums.insert(-1);
  for (int i = 0; i < 4 *N; i++)
  {
        if (!(sAt[i][0] == 0 && sAt[i][1] == 0))
        {
            if (sAt[i][0] < 0) nums.insert(sAt[i][0]);
            if (sAt[i][1] < 0) nums.insert(sAt[i][1]);


        }
  }
  int cnum = -1;
  for (auto it = nums.rbegin(); it != nums.rend(); it++)
  {
    turnTo[*it] = cnum;
    cnum--;
  }

    for (int i = 0; i < 4 *N; i++)
  {
        if (!(sAt[i][0] == 0 && sAt[i][1] == 0))
        {
            if (sAt[i][0] < 0) x.push_back(turnTo[sAt[i][0]]);
            else x.push_back(sAt[i][0]);
            if (sAt[i][1] < 0) y.push_back(turnTo[sAt[i][1]]);
            else y.push_back(sAt[i][1]);
        }
  }

  answer(c, x, y);
}

/*
2 2
1 2

*/

Subtask #1
0 / 2.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 204 KB Output is partially correct
2 Correct 158 ms 20532 KB Output is correct
3 Partially correct 353 ms 39140 KB Output is partially correct
4 Partially correct 383 ms 39768 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 204 KB Output is partially correct
2 Correct 158 ms 20532 KB Output is correct
3 Partially correct 353 ms 39140 KB Output is partially correct
4 Partially correct 383 ms 39768 KB Output is partially correct
5 Partially correct 383 ms 40300 KB Output is partially correct
6 Partially correct 356 ms 39964 KB Output is partially correct
7 Partially correct 377 ms 40100 KB Output is partially correct
8 Partially correct 346 ms 39968 KB Output is partially correct
9 Partially correct 372 ms 39036 KB Output is partially correct
10 Partially correct 415 ms 39840 KB Output is partially correct
11 Partially correct 340 ms 39772 KB Output is partially correct
12 Partially correct 349 ms 39076 KB Output is partially correct
13 Correct 165 ms 20692 KB Output is correct
14 Partially correct 369 ms 39164 KB Output is partially correct
15 Partially correct 383 ms 39176 KB Output is partially correct
16 Partially correct 9 ms 1484 KB Output is partially correct
17 Correct 157 ms 20512 KB Output is correct
18 Correct 164 ms 20468 KB Output is correct
19 Partially correct 356 ms 38960 KB Output is partially correct
20 Partially correct 378 ms 39828 KB Output is partially correct
21 Partially correct 341 ms 39872 KB Output is partially correct
22 Partially correct 347 ms 39892 KB Output is partially correct