oj.uz

Submission #680341

# Submission time Handle Problem Language Result Execution time Memory
680341 2023-01-10T15:39:11 Z MasterTaster Mechanical Doll (IOI18_doll) C++14
100 / 100
 210 ms 29776 KB 
#include "doll.h"
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

#define ll long long
#define pb push_back
#define pii pair<int, int>
#define xx first
#define yy second
#define MAXN 200010

using namespace std;

int n, m, k, logg;
vector<int> a, X, Y;
int which[400010];

int s=-1;
map<int, int> lc, rc;
ll two[30];
vector<int> all;

void solve(int sw, int l, int r, int cnt)
{
    if ((r-l)==1)
    {
        if (cnt>=1)
            rc[sw]=which[r];
        else
            rc[sw]=-1;
        if (cnt==2)
            lc[sw]=which[l];
        else
            lc[sw]=-1;
        return;
    }

    if ((r-l+1)/2>=cnt)
    {
        lc[sw]=-1;
        rc[sw]=--s;
        int mid=l+(r-l)/2;
        solve(rc[sw], mid+1, r, cnt);
    }
    else if (cnt>(r-l+1)/2)
    {
        lc[sw]=--s;
        rc[sw]=--s;
        int mid=l+(r-l)/2;
        solve(lc[sw], l, mid, cnt-(mid-l+1));
        solve(rc[sw], mid+1, r, (mid-l+1));
    }
}

void findorder()
{
    two[0]=1;
    for (int i=1; i<=20; i++) two[i]=(two[i-1]*2);

    for (int i=0; i<k; i++) {
        int step = 0; int ii=i;
        int ress=0;
        while (i) {
            int cif = i % 2;
            i /= 2;
            ress = ress + cif * two[logg - 1 - step];
            step++;
        }
        i=ii;
        all.pb(ress+1);
    }

    //for (int i=0; i<all.size(); i++) cout<<all[i]<<" ";
    //cout<<endl;

    int j=0;
    for (int i=0; i<all.size(); i++)
    {
        if (all[i]>(k-n)) { /*cout<<all[i]<<" "<<a[j]<<endl;*/ which[all[i]]=a[j++]; }
    }
}

void create_circuit(int M, std::vector<int> A) {
    for (int i=0; i<A.size(); i++) a.pb(A[i]);
    a.pb(0);
    m=M; n = a.size();

    k=1; logg=0;
    while (k<n) { k*=2; logg++; }

    vector<int> C(m+1);
    for (int i=0; i<=m; i++) C[i]=-1;

    findorder();
    solve(s, 1, k, n);

    for (int i=-1; i>=s; i--)
    {
        X.pb(lc[i]);
        Y.pb(rc[i]);
    }

    answer(C, X, Y);
}
/*
5 5
1 3 1 4 1
 */

Compilation message

doll.cpp: In function 'void findorder()':
doll.cpp:79:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for (int i=0; i<all.size(); i++)
      |                   ~^~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:86:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for (int i=0; i<A.size(); i++) a.pb(A[i]);
      |                   ~^~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 62 ms 11040 KB Output is correct
3 Correct 57 ms 11280 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1492 KB Output is correct
6 Correct 85 ms 15416 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 62 ms 11040 KB Output is correct
3 Correct 57 ms 11280 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1492 KB Output is correct
6 Correct 85 ms 15416 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 110 ms 20952 KB Output is correct
9 Correct 106 ms 21456 KB Output is correct
10 Correct 161 ms 29776 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 62 ms 11040 KB Output is correct
3 Correct 57 ms 11280 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1492 KB Output is correct
6 Correct 85 ms 15416 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 110 ms 20952 KB Output is correct
9 Correct 106 ms 21456 KB Output is correct
10 Correct 161 ms 29776 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 156 ms 29164 KB Output is correct
15 Correct 108 ms 20400 KB Output is correct
16 Correct 165 ms 28972 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 158 ms 29376 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 104 ms 19400 KB Output is correct
3 Correct 99 ms 19412 KB Output is correct
4 Correct 144 ms 28104 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 104 ms 19400 KB Output is correct
3 Correct 99 ms 19412 KB Output is correct
4 Correct 144 ms 28104 KB Output is correct
5 Correct 158 ms 28884 KB Output is correct
6 Correct 154 ms 28476 KB Output is correct
7 Correct 184 ms 28544 KB Output is correct
8 Correct 149 ms 28292 KB Output is correct
9 Correct 99 ms 19432 KB Output is correct
10 Correct 151 ms 28240 KB Output is correct
11 Correct 146 ms 28064 KB Output is correct
12 Correct 99 ms 19672 KB Output is correct
13 Correct 105 ms 20112 KB Output is correct
14 Correct 115 ms 20164 KB Output is correct
15 Correct 110 ms 20344 KB Output is correct
16 Correct 3 ms 852 KB Output is correct
17 Correct 112 ms 18536 KB Output is correct
18 Correct 104 ms 19780 KB Output is correct
19 Correct 104 ms 19616 KB Output is correct
20 Correct 152 ms 28276 KB Output is correct
21 Correct 146 ms 28004 KB Output is correct
22 Correct 210 ms 27992 KB Output is correct