oj.uz

Submission #293187

# Submission time Handle Problem Language Result Execution time Memory
293187 2020-09-07T17:53:46 Z Fasho Mechanical Doll (IOI18_doll) C++14
74.8161 / 100
 189 ms 25852 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)
    {
        --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;
    int uu = bil(l, m, pos, d + 1);
    ansx[-u - 1] = uu;
    uu = bil(m + 1, r, pos + (1 << d), d + 1);
    ansy[-u - 1] = uu;
    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 8 ms 9676 KB Output is correct
2 Correct 79 ms 15612 KB Output is correct
3 Correct 46 ms 15160 KB Output is correct
4 Correct 9 ms 9676 KB Output is correct
5 Correct 21 ms 10948 KB Output is correct
6 Correct 83 ms 18004 KB Output is correct
7 Correct 9 ms 9676 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9676 KB Output is correct
2 Correct 79 ms 15612 KB Output is correct
3 Correct 46 ms 15160 KB Output is correct
4 Correct 9 ms 9676 KB Output is correct
5 Correct 21 ms 10948 KB Output is correct
6 Correct 83 ms 18004 KB Output is correct
7 Correct 9 ms 9676 KB Output is correct
8 Correct 127 ms 20408 KB Output is correct
9 Correct 152 ms 20732 KB Output is correct
10 Correct 189 ms 25852 KB Output is correct
11 Correct 9 ms 9652 KB Output is correct
12 Correct 9 ms 9676 KB Output is correct
13 Correct 7 ms 9676 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9676 KB Output is correct
2 Correct 79 ms 15612 KB Output is correct
3 Correct 46 ms 15160 KB Output is correct
4 Correct 9 ms 9676 KB Output is correct
5 Correct 21 ms 10948 KB Output is correct
6 Correct 83 ms 18004 KB Output is correct
7 Correct 9 ms 9676 KB Output is correct
8 Correct 127 ms 20408 KB Output is correct
9 Correct 152 ms 20732 KB Output is correct
10 Correct 189 ms 25852 KB Output is correct
11 Correct 9 ms 9652 KB Output is correct
12 Correct 9 ms 9676 KB Output is correct
13 Correct 7 ms 9676 KB Output is correct
14 Correct 169 ms 23452 KB Output is correct
15 Incorrect 103 ms 18056 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9624 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 8 ms 9676 KB Output is correct
4 Correct 7 ms 9676 KB Output is correct
5 Correct 7 ms 9692 KB Output is correct
6 Correct 10 ms 9660 KB Output is correct
7 Correct 8 ms 9676 KB Output is correct
8 Correct 8 ms 9600 KB Output is correct

Subtask #5
14.3066098836 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 8 ms 9580 KB Output is partially correct
2 Correct 69 ms 16304 KB Output is correct
3 Partially correct 72 ms 16624 KB Output is partially correct
4 Correct 108 ms 19828 KB Output is correct

Subtask #6
44.5094529712 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 8 ms 9580 KB Output is partially correct
2 Correct 69 ms 16304 KB Output is correct
3 Partially correct 72 ms 16624 KB Output is partially correct
4 Correct 108 ms 19828 KB Output is correct
5 Correct 153 ms 23372 KB Output is correct
6 Correct 135 ms 22616 KB Output is correct
7 Correct 138 ms 22660 KB Output is correct
8 Correct 137 ms 22088 KB Output is correct
9 Partially correct 69 ms 16696 KB Output is partially correct
10 Correct 121 ms 20808 KB Output is correct
11 Partially correct 113 ms 21660 KB Output is partially correct
12 Partially correct 95 ms 17800 KB Output is partially correct
13 Correct 93 ms 18000 KB Output is correct
14 Partially correct 95 ms 18316 KB Output is partially correct
15 Partially correct 114 ms 18628 KB Output is partially correct
16 Partially correct 11 ms 9932 KB Output is partially correct
17 Correct 73 ms 17072 KB Output is correct
18 Correct 106 ms 17104 KB Output is correct
19 Partially correct 86 ms 17440 KB Output is partially correct
20 Correct 129 ms 20820 KB Output is correct
21 Correct 114 ms 21188 KB Output is correct
22 Correct 114 ms 20512 KB Output is correct