oj.uz

Submission #577569

# Submission time Handle Problem Language Result Execution time Memory
577569 2022-06-15T05:26:27 Z MadokaMagicaFan Mechanical Doll (IOI18_doll) C++14
100 / 100
 252 ms 24148 KB 
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;
const int md2 = 998244353;

#define sz(v)                       ((int)v.size())
#define pb                          push_back

#define pry                         cout << "YES\n"
#define prn                         cout << "NO\n"
#define endl                        '\n'

#define fst                         first
#define scn                         second
/* #define ONPC */

const int M = 1e5;
vector<int> v[M+5], x, y, c;
const int S = 4e5;
const int P = 2e7;
vector<int> reala;
map<int,int> compress;
int p = 0;

void answer(vector<int> C, vector<int> X, vector<int> Y);

int
news()
{
    x.pb(0);
    y.pb(0);
    return sz(x);
}

void
dfs2(int l, int r, int s, int k)
{
    if (l == r) {
        reala[l] = s;
        return;
    }
    int mid = (l+r)>>1;
    dfs2(l,mid,s,k+1);
    dfs2(mid+1,r,s+(1<<k),k+1);
}

int
dfs(int l, int r, int ind, vector<int>& a,int k)
{
    if (l == r) {
        if ((1<<x[ind-1])-1-l >= sz(a))
            return -ind;
        else
            return a[compress[reala[l]]];
        /* if (l >= sz(a)-1) { */
        /*     if (l == (1<<x[ind-1])-1) */
        /*         return a[sz(a)-1]; */
        /*     else */
        /*         return -ind; */
        /* } */
    }

    int mid = (l+r)>>1;
    int _x = dfs(l,mid,ind,a,k+1);
    int _y = dfs(mid+1,r,ind,a,k+1);
    if (_x == _y)
        return _x;
    int index = news();
    p += (1<<(x[ind-1]-k));
    x[index-1] = _x;
    y[index-1] = _y;

    return -index;
}

int
donode(vector<int> &a)
{
    if (sz(a) == 1) return 0;
    int l = 31 - __builtin_clz(sz(a));
    if (sz(a) ^ (1<<l))
        ++l;
    int ind = news();
    x[ind-1] = l;
    p += (1<<(l));

    reala.resize(1<<l);
    dfs2(0,(1<<l)-1,0,0);
    vector<int> normalization;
    for (int i = 0; i < sz(a); ++i) {
        normalization.pb(reala[(1<<l)-1-i]);
    }
    sort(normalization.begin(), normalization.end());
    for (int i = 0; i < sz(a); ++i) {
        compress[normalization[i]] = i;
    }


    int mid = ((1<<l)-1)>>1;
    int _x = dfs(0,mid,ind,a,1);
    int _y = dfs(mid+1,(1<<l)-1,ind,a,1);

    x[ind-1] = _x;
    y[ind-1] = _y;

    return -ind;
}

void
create_circuit(int m, vector<int> a)
{
    int n = sz(a);
    vector<int> a2;
    for (int j = 1; j < n; ++j) {
        a2.pb(a[j]);
    }
    a2.pb(0);
    
    int indx = donode(a2);

    c.assign(m+1,indx);
    c[0] = a[0];


    /* assert(sz(x)<=n*2); */
    /* cout << sz(x) << ' ' << n << ' ' << n + 31 - __builtin_clz(n) << endl; */
    /* return; */
    /* assert(sz(x)<=S); */
    assert(sz(x)<=n+log2(n));
    /* return; */
    assert(p<=P);
    answer(c,x,y);

    return;
}


#ifdef ONPC
void
answer(vector<int> C, vector<int> X, vector<int> Y)
{
    int s = sz(X);
    int m = sz(C)-1;

    for (int i = 0; i < sz(C); ++i) {
        assert(C[i] <= m);
        assert(C[i] >= -s);
    }
    for (int i = 0; i < sz(X); ++i) {
        assert(X[i] <= m);
        assert(X[i] >= -s);
        assert(Y[i] <= m);
        assert(Y[i] >= -s);
    }

    vector<int> ans;
    vector<bool> state(sz(X),0);

    /* for (int i = 0; i < sz(X); ++i) { */
    /*     cout << "-" << i+1 << ": " << X[i] << ' ' << Y[i]<< endl; */
    /* } */

    int tg = C[0];

    while (tg) {
        if (tg >= 0) {
            ans.pb(tg);
            tg = C[tg];
        } else {
            int index = -tg-1;
            if (state[index]==0) tg = X[index];
            else                 tg = Y[index];
            state[index] = !state[index];
        }
    }

    for (int i = 0; i < sz(X); ++i) {
        if (state[i]) {
            cout << i << endl;
            cout << "Error\n";
            return;
        }
    }
    cout << sz(ans) << endl;
    for (int i = 0; i < sz(ans); ++i) {
        cout << ans[i] << ' ';
    }
    cout << endl;
    return;
}

void
solve()
{
    int n, m;
    cin >> m;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    
    cout << m << ' ';
    create_circuit(m, a);
}

int32_t
main(int argc, char **argv)
{
    if (argc >= 2) {
        freopen(argv[1], "r", stdin);
    } else
        ios_base::sync_with_stdio(0);cin.tie(0);
    int t = 1;
    /* cin >> t; */
    while(t--)
        solve();
}
#endif

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 53 ms 9660 KB Output is correct
3 Correct 53 ms 10092 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 9 ms 3796 KB Output is correct
6 Correct 99 ms 13476 KB Output is correct
7 Correct 2 ms 2648 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 53 ms 9660 KB Output is correct
3 Correct 53 ms 10092 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 9 ms 3796 KB Output is correct
6 Correct 99 ms 13476 KB Output is correct
7 Correct 2 ms 2648 KB Output is correct
8 Correct 107 ms 16444 KB Output is correct
9 Correct 115 ms 17500 KB Output is correct
10 Correct 252 ms 24148 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 53 ms 9660 KB Output is correct
3 Correct 53 ms 10092 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 9 ms 3796 KB Output is correct
6 Correct 99 ms 13476 KB Output is correct
7 Correct 2 ms 2648 KB Output is correct
8 Correct 107 ms 16444 KB Output is correct
9 Correct 115 ms 17500 KB Output is correct
10 Correct 252 ms 24148 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 239 ms 23632 KB Output is correct
15 Correct 130 ms 16476 KB Output is correct
16 Correct 226 ms 23344 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 2 ms 2644 KB Output is correct
19 Correct 2 ms 2652 KB Output is correct
20 Correct 241 ms 23880 KB Output is correct
21 Correct 2 ms 2644 KB Output is correct
22 Correct 2 ms 2596 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 83 ms 11284 KB Output is correct
3 Correct 99 ms 11840 KB Output is correct
4 Correct 180 ms 16132 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 83 ms 11284 KB Output is correct
3 Correct 99 ms 11840 KB Output is correct
4 Correct 180 ms 16132 KB Output is correct
5 Correct 242 ms 21724 KB Output is correct
6 Correct 237 ms 21488 KB Output is correct
7 Correct 225 ms 21624 KB Output is correct
8 Correct 234 ms 21236 KB Output is correct
9 Correct 123 ms 14052 KB Output is correct
10 Correct 219 ms 20312 KB Output is correct
11 Correct 215 ms 20792 KB Output is correct
12 Correct 108 ms 15160 KB Output is correct
13 Correct 117 ms 14660 KB Output is correct
14 Correct 106 ms 15376 KB Output is correct
15 Correct 110 ms 15376 KB Output is correct
16 Correct 4 ms 3028 KB Output is correct
17 Correct 105 ms 14336 KB Output is correct
18 Correct 117 ms 14268 KB Output is correct
19 Correct 122 ms 15084 KB Output is correct
20 Correct 231 ms 20952 KB Output is correct
21 Correct 230 ms 20684 KB Output is correct
22 Correct 226 ms 20736 KB Output is correct