oj.uz

Submission #680334

# Submission time Handle Problem Language Result Execution time Memory
680334 2023-01-10T15:15:33 Z MasterTaster Mechanical Doll (IOI18_doll) C++14
12 / 100
 924 ms 262144 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 MAXM 100010
#define MAXN 200010
#define INF 1000000

using namespace std;

int n, m, mcnt, cnt, cntleft, c[MAXM], k, logg;
vector<int> a, X, Y;
int which[MAXN];

/*struct Switch{
    int id, p, l, r, st; ///serial num, parent, left child, right child, state
    Switch() { id=-1; p=-1; l=INF; r=INF; st=0; }
};
vector<Switch> sww;*/
int s=-1;
map<int, int> lc, rc;
int two[30];
vector<int> all;

void solve(int sw, int l, int r, int cnt)
{
    if (r-l==1)
    {
        rc[sw]=which[r];
        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));
    }
}

map<int, int> f;
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:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for (int i=0; i<all.size(); i++)
      |                   ~^~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:91:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     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 1 ms 340 KB Output is correct
2 Correct 70 ms 11700 KB Output is correct
3 Correct 58 ms 11696 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 9 ms 1492 KB Output is correct
6 Correct 91 ms 16220 KB Output is correct
7 Correct 0 ms 308 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 70 ms 11700 KB Output is correct
3 Correct 58 ms 11696 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 9 ms 1492 KB Output is correct
6 Correct 91 ms 16220 KB Output is correct
7 Correct 0 ms 308 KB Output is correct
8 Runtime error 898 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 70 ms 11700 KB Output is correct
3 Correct 58 ms 11696 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 9 ms 1492 KB Output is correct
6 Correct 91 ms 16220 KB Output is correct
7 Correct 0 ms 308 KB Output is correct
8 Runtime error 898 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 924 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 924 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -