oj.uz

Submission #293246

# Submission time Handle Problem Language Result Execution time Memory
293246 2020-09-07T19:51:29 Z SamAnd Mechanical Doll (IOI18_doll) C++17
100 / 100
 235 ms 25804 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const int N = 200005;
 
int n, m;
 
int z;
vector<int> ans;
vector<int> ansx;
vector<int> ansy;
 
bool stg0(int x)
{
    while (x % 2 == 0)
        x /= 2;
    return x == 1;
}
 
vector<int> v[N], vi[N];
int q;
int f;
int bil(int l, int r, int pos, int d)
{
    if (r < q)
    {
      	return f;
        --z;
        ansx.push_back(z);
        ansy.push_back(f);
        return z;
    }
    if (l == r)
    {
        return pos;
    }
    int m = (l + r) / 2;
    int u = --z;
    ansx.push_back(0);
    ansy.push_back(0);
    if (d == 0)
        f = u;
    ansx[-u - 1] = bil(l, m, pos, d + 1);
    ansy[-u - 1] = bil(m + 1, r, pos + (1 << d), d + 1);
    return u;
}
 
bool c[N];
void create_circuit(int M_, std::vector<int> A)
{
    n = sz(A);
    m = M_;
 
    for (int i = 0; i < n; ++i)
    {
        if (i < n - 1)
            v[A[i]].push_back(A[i + 1]);
        else
            v[A[i]].push_back(0);
        vi[A[i]].push_back(i);
    }
 
    for (int i = 1; i <= m; ++i)
    {
        if (sz(v[i]) == 1)
        {
            --n;
            c[vi[i][0]] = true;
        }
    }
 
    if (n == 0)
    {
        ans.push_back(A[0]);
        for (int x = 1; x <= m; ++x)
        {
            if (sz(v[x]) == 1)
                ans.push_back(v[x][0]);
            else
                ans.push_back(0);
        }
        answer(ans, ansx, ansy);
        return;
    }
 
    while (!stg0(q + n))
        ++q;
    bil(0, q + n - 1, 0, 0);
    vector<pair<int, pair<int, int> > > vv;
    for (int i = 0; i < sz(ansx); ++i)
    {
        if (ansx[i] >= 0)
            vv.push_back(m_p(ansx[i], m_p(i, 0)));
        if (ansy[i] >= 0)
            vv.push_back(m_p(ansy[i], m_p(i, 1)));
    }
    sort(all(vv));
 
    assert(sz(vv) == n);
    int j = 0;
    for (int i = 0; i < n; ++i)
    {
        while (c[j])
            ++j;
        if (j < sz(A) - 1)
        {
            if (vv[i].se.se == 0)
                ansx[vv[i].se.fi] = A[j + 1];
            else
                ansy[vv[i].se.fi] = A[j + 1];
        }
        else
        {
            if (vv[i].se.se == 0)
                ansx[vv[i].se.fi] = 0;
            else
                ansy[vv[i].se.fi] = 0;
        }
        ++j;
    }
 
    n = sz(A);
    ans.push_back(A[0]);
    for (int x = 1; x <= m; ++x)
    {
        if (sz(v[x]) == 1)
            ans.push_back(v[x][0]);
        else
            ans.push_back(f);
    }
    answer(ans, ansx, ansy);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9696 KB Output is correct
2 Correct 72 ms 15576 KB Output is correct
3 Correct 80 ms 15192 KB Output is correct
4 Correct 8 ms 9676 KB Output is correct
5 Correct 18 ms 10948 KB Output is correct
6 Correct 120 ms 18044 KB Output is correct
7 Correct 8 ms 9592 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9696 KB Output is correct
2 Correct 72 ms 15576 KB Output is correct
3 Correct 80 ms 15192 KB Output is correct
4 Correct 8 ms 9676 KB Output is correct
5 Correct 18 ms 10948 KB Output is correct
6 Correct 120 ms 18044 KB Output is correct
7 Correct 8 ms 9592 KB Output is correct
8 Correct 148 ms 20484 KB Output is correct
9 Correct 131 ms 20664 KB Output is correct
10 Correct 200 ms 25804 KB Output is correct
11 Correct 7 ms 9676 KB Output is correct
12 Correct 8 ms 9676 KB Output is correct
13 Correct 7 ms 9676 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9696 KB Output is correct
2 Correct 72 ms 15576 KB Output is correct
3 Correct 80 ms 15192 KB Output is correct
4 Correct 8 ms 9676 KB Output is correct
5 Correct 18 ms 10948 KB Output is correct
6 Correct 120 ms 18044 KB Output is correct
7 Correct 8 ms 9592 KB Output is correct
8 Correct 148 ms 20484 KB Output is correct
9 Correct 131 ms 20664 KB Output is correct
10 Correct 200 ms 25804 KB Output is correct
11 Correct 7 ms 9676 KB Output is correct
12 Correct 8 ms 9676 KB Output is correct
13 Correct 7 ms 9676 KB Output is correct
14 Correct 182 ms 23580 KB Output is correct
15 Correct 116 ms 17988 KB Output is correct
16 Correct 167 ms 22100 KB Output is correct
17 Correct 9 ms 9692 KB Output is correct
18 Correct 9 ms 9676 KB Output is correct
19 Correct 8 ms 9676 KB Output is correct
20 Correct 235 ms 24108 KB Output is correct
21 Correct 9 ms 9676 KB Output is correct
22 Correct 9 ms 9676 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9628 KB Output is correct
2 Correct 7 ms 9672 KB Output is correct
3 Correct 8 ms 9676 KB Output is correct
4 Correct 10 ms 9676 KB Output is correct
5 Correct 7 ms 9676 KB Output is correct
6 Correct 9 ms 9676 KB Output is correct
7 Correct 7 ms 9696 KB Output is correct
8 Correct 7 ms 9696 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9676 KB Output is correct
2 Correct 70 ms 16304 KB Output is correct
3 Correct 69 ms 16648 KB Output is correct
4 Correct 110 ms 19868 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9676 KB Output is correct
2 Correct 70 ms 16304 KB Output is correct
3 Correct 69 ms 16648 KB Output is correct
4 Correct 110 ms 19868 KB Output is correct
5 Correct 158 ms 23368 KB Output is correct
6 Correct 150 ms 22588 KB Output is correct
7 Correct 145 ms 22608 KB Output is correct
8 Correct 132 ms 22056 KB Output is correct
9 Correct 69 ms 16728 KB Output is correct
10 Correct 124 ms 20804 KB Output is correct
11 Correct 113 ms 21604 KB Output is correct
12 Correct 79 ms 17940 KB Output is correct
13 Correct 101 ms 18052 KB Output is correct
14 Correct 90 ms 18352 KB Output is correct
15 Correct 96 ms 18648 KB Output is correct
16 Correct 9 ms 9932 KB Output is correct
17 Correct 75 ms 17072 KB Output is correct
18 Correct 73 ms 17072 KB Output is correct
19 Correct 74 ms 17444 KB Output is correct
20 Correct 126 ms 20820 KB Output is correct
21 Correct 121 ms 21160 KB Output is correct
22 Correct 111 ms 20480 KB Output is correct