oj.uz

Submission #680340

# Submission time Handle Problem Language Result Execution time Memory
680340 2023-01-10T15:38:19 Z MasterTaster Mechanical Doll (IOI18_doll) C++14
100 / 100
 194 ms 31228 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 500010

using namespace std;

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

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 63 ms 11088 KB Output is correct
3 Correct 60 ms 11316 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 11 ms 1492 KB Output is correct
6 Correct 85 ms 15432 KB Output is correct
7 Correct 1 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 63 ms 11088 KB Output is correct
3 Correct 60 ms 11316 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 11 ms 1492 KB Output is correct
6 Correct 85 ms 15432 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 117 ms 20872 KB Output is correct
9 Correct 110 ms 22288 KB Output is correct
10 Correct 154 ms 31228 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 312 KB Output is correct
13 Correct 0 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 63 ms 11088 KB Output is correct
3 Correct 60 ms 11316 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 11 ms 1492 KB Output is correct
6 Correct 85 ms 15432 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 117 ms 20872 KB Output is correct
9 Correct 110 ms 22288 KB Output is correct
10 Correct 154 ms 31228 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 312 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 159 ms 30724 KB Output is correct
15 Correct 113 ms 21344 KB Output is correct
16 Correct 155 ms 30464 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 312 KB Output is correct
20 Correct 165 ms 30872 KB Output is correct
21 Correct 1 ms 316 KB Output is correct
22 Correct 0 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 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 1 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 19444 KB Output is correct
3 Correct 103 ms 20360 KB Output is correct
4 Correct 152 ms 29460 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 19444 KB Output is correct
3 Correct 103 ms 20360 KB Output is correct
4 Correct 152 ms 29460 KB Output is correct
5 Correct 162 ms 30248 KB Output is correct
6 Correct 194 ms 29988 KB Output is correct
7 Correct 161 ms 30288 KB Output is correct
8 Correct 169 ms 29844 KB Output is correct
9 Correct 110 ms 20356 KB Output is correct
10 Correct 165 ms 29848 KB Output is correct
11 Correct 148 ms 29536 KB Output is correct
12 Correct 101 ms 20580 KB Output is correct
13 Correct 103 ms 21132 KB Output is correct
14 Correct 104 ms 21152 KB Output is correct
15 Correct 115 ms 21240 KB Output is correct
16 Correct 3 ms 980 KB Output is correct
17 Correct 102 ms 19464 KB Output is correct
18 Correct 101 ms 20588 KB Output is correct
19 Correct 102 ms 20668 KB Output is correct
20 Correct 159 ms 29628 KB Output is correct
21 Correct 185 ms 29544 KB Output is correct
22 Correct 153 ms 29584 KB Output is correct