oj.uz

Submission #966134

# Submission time Handle Problem Language Result Execution time Memory
966134 2024-04-19T12:16:51 Z anango Mechanical Doll (IOI18_doll) C++14
100 / 100
 213 ms 27200 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
int m;
int n;
int MAXN=1;
int depth=0;
vector<int> C;
vector<int> X;
vector<int> Y;
 
void update(int pos, int val) {
    pos+=MAXN; 
    //cout <<"UPDATED " <<  pos <<" "<< val << endl;
    if (pos%2==0) {
        X[pos/2] = val;
    }
    else { 
        Y[pos/2] = val;
    }
    pos/=2;
    while (pos>1) {
        int par=pos/2;
        if (pos%2==0) {
            X[par] = -pos;
        }
        else {
            Y[par] = -pos;
        }
        pos=par;
    }
}
int binrev(int v) {
    vector<int> bits;
    while (v) {
        bits.push_back(v%2);
        v/=2;
    }
 
    int x=0;
    for (auto i:bits) {
        x*=2;
        x+=i;
    }
    return x;
}
int timer(int k) {
    vector<int> bits;
    for (int i=0; i<depth; i++) {
        bits.push_back(k%2);
        k/=2;
    }
 
    int x=0;
    for (auto i:bits) {
        x*=2;
        x+=i;
    }
    return x;
}
vector<int> times;
void create_circuit(signed M, vector<signed> A) {
    int N = A.size();
    N++;
    A.push_back(0);
    //top of the tree = 1
    //sons of i are 2*i and 2*i+1
    for (int i=1; i<100; i++) {
        MAXN*=2;
        if (MAXN>=N) {
            depth=i;
            break;
        }
    }
    times=vector<int>(MAXN,-1);
    for (int i=0; i<MAXN; i++) {
        times[i] = timer(i);
    }
    for (int i=0; i<8; i++) {
        //cout << i <<" " << time(i) << endl;
    }
    int S=MAXN;
    C=vector<int>(M+1,-1);
    X=vector<int>(S+1,-1);
    Y=vector<int>(S+1,-1);
    C[0] = -1;
    int lef=MAXN/2;
    int ri=N-lef;
    vector<int> elems;
    for (int i=0; i<lef; i++) {
        //cout << i <<" " << binrev(i) << endl;
        elems.push_back(i);
    }
    for (int i=MAXN-ri; i<MAXN; i++) {
        elems.push_back(i);
    }
    
    sort(elems.begin(), elems.end(), [&](const int a, const int b) {
        return times[a]<times[b];
    });
    //cout << "ELEMS" << endl;
    //for (auto i:elems) {
   //     cout << i <<" ";
   // }
    //cout << endl;
    assert(elems.size()==N);
    for (int i=0; i<elems.size(); i++) {
        update(elems[i], A[i]);
    }
    //cout << "DONE1" << " " << M << " " << S << " " << S <<" " <<endl;
    vector<signed> C2;
    vector<signed> X2;
    vector<signed> Y2;
    //cout << "DONE3" << endl;
    for (int i=0; i<C.size(); i++) {
        //cout << i <<" " << C.size() << " " << C[i] << " " << M+1 << endl;
        C2.push_back(C[i]);
    }
    for (int i=1; i<=S; i++) {
        X2.push_back(X[i]);
    }
    for (int i=1; i<=S; i++) {
        Y2.push_back(Y[i]);
    }   
    //cout << "DONE2" << endl;
    
    set<int> used;
    for (auto i:X2) {
        if (i>=0) {
            continue;
        }
        used.insert(-i);
    }
    for (auto i:Y2) {
        if (i>=0) {
            continue;
        }
        used.insert(-i);
    }
    vector<int> vued;
    for (auto i:used) {
        vued.push_back(i);
    }
    //cout << used.size() << endl;
    int us = used.size();
    vector<int> revmap(S+3,-1);
    for (int i=0; i<us; i++) {
        //cout << i <<" " << vued[i] << endl;
        revmap[vued[i]] = i;
    }
    //cout << "DONE" << endl;
    vector<signed> C3(M+1);
    for (int i=0; i<=M; i++) {
        C3[i] = C[i];
    }
    vector<signed> X3(us,-888);
    for (int i=0; i<S; i++) {
        if (!(used.count(i+1))) {
            continue;
        }
        X3[revmap[i+1]] = (X2[i]<0?-revmap[-X2[i]]-1:X2[i]);
    }
    vector<signed> Y3(us,-888);
    for (int i=0; i<S; i++) {
        if (!(used.count(i+1))) {
            continue;
        }
        //cout << "doing " << i <<" " << revmap[i+1] <<" "<< -Y2[i] << endl;
        Y3[revmap[i+1]] = (Y2[i]<0?-revmap[-Y2[i]]-1:Y2[i]);
    }
    //cout << "original" << endl;
    for (int i=0; i<S; i++) {
        //cout << i <<" " << X2[i] <<" " << Y2[i] << endl;
    }
    //cout << "compressed" << endl;
    for (int i=0; i<us; i++) {
        //cout << i <<" " << X3[i] <<" " << Y3[i] << endl;
    }
    
    //cout << "DONE2" << endl;
    
    A.pop_back();
    N--;
    //cout << "DONE" << endl;
    
    answer(C3, X3, Y3);
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from doll.cpp:2:
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:106:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  106 |     assert(elems.size()==N);
      |            ~~~~~~~~~~~~^~~
doll.cpp:107:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for (int i=0; i<elems.size(); i++) {
      |                   ~^~~~~~~~~~~~~
doll.cpp:115:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for (int i=0; i<C.size(); i++) {
      |                   ~^~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 73 ms 11564 KB Output is correct
3 Correct 77 ms 10920 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 8 ms 2516 KB Output is correct
6 Correct 95 ms 14792 KB Output is correct
7 Correct 1 ms 344 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 73 ms 11564 KB Output is correct
3 Correct 77 ms 10920 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 8 ms 2516 KB Output is correct
6 Correct 95 ms 14792 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 167 ms 20324 KB Output is correct
9 Correct 156 ms 20780 KB Output is correct
10 Correct 186 ms 27200 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 428 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 73 ms 11564 KB Output is correct
3 Correct 77 ms 10920 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 8 ms 2516 KB Output is correct
6 Correct 95 ms 14792 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 167 ms 20324 KB Output is correct
9 Correct 156 ms 20780 KB Output is correct
10 Correct 186 ms 27200 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 428 KB Output is correct
14 Correct 186 ms 26820 KB Output is correct
15 Correct 142 ms 19280 KB Output is correct
16 Correct 181 ms 26180 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 432 KB Output is correct
20 Correct 193 ms 27152 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 432 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 152 ms 18800 KB Output is correct
3 Correct 153 ms 18784 KB Output is correct
4 Correct 181 ms 25152 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 152 ms 18800 KB Output is correct
3 Correct 153 ms 18784 KB Output is correct
4 Correct 181 ms 25152 KB Output is correct
5 Correct 184 ms 26180 KB Output is correct
6 Correct 187 ms 25684 KB Output is correct
7 Correct 182 ms 25668 KB Output is correct
8 Correct 183 ms 25408 KB Output is correct
9 Correct 139 ms 18788 KB Output is correct
10 Correct 185 ms 25416 KB Output is correct
11 Correct 184 ms 25156 KB Output is correct
12 Correct 143 ms 18768 KB Output is correct
13 Correct 139 ms 18888 KB Output is correct
14 Correct 139 ms 19016 KB Output is correct
15 Correct 140 ms 19272 KB Output is correct
16 Correct 4 ms 860 KB Output is correct
17 Correct 101 ms 16940 KB Output is correct
18 Correct 142 ms 18816 KB Output is correct
19 Correct 137 ms 18840 KB Output is correct
20 Correct 213 ms 25160 KB Output is correct
21 Correct 176 ms 25228 KB Output is correct
22 Correct 182 ms 25264 KB Output is correct