oj.uz

Submission #966096

# Submission time Handle Problem Language Result Execution time Memory
966096 2024-04-19T11:28:41 Z anango Mechanical Doll (IOI18_doll) C++14
37 / 100
 145 ms 19540 KB 
#include "doll.h"
#include <bits/stdc++.h>
#define int long long
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;
    
    A.pop_back();
    //cout << "DONE" << endl;
    answer(C2, X2, Y2);
}

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:107:24: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  107 |     assert(elems.size()==N);
      |            ~~~~~~~~~~~~^~~
doll.cpp:108:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |     for (int i=0; i<elems.size(); i++) {
      |                   ~^~~~~~~~~~~~~
doll.cpp:116:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |     for (int i=0; i<C.size(); i++) {
      |                   ~^~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Output is partially correct
2 Partially correct 115 ms 16952 KB Output is partially correct
3 Partially correct 138 ms 17088 KB Output is partially correct
4 Partially correct 132 ms 18240 KB Output is partially correct

Subtask #6
28.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Output is partially correct
2 Partially correct 115 ms 16952 KB Output is partially correct
3 Partially correct 138 ms 17088 KB Output is partially correct
4 Partially correct 132 ms 18240 KB Output is partially correct
5 Partially correct 139 ms 19540 KB Output is partially correct
6 Partially correct 145 ms 19296 KB Output is partially correct
7 Partially correct 139 ms 19464 KB Output is partially correct
8 Partially correct 136 ms 18960 KB Output is partially correct
9 Partially correct 120 ms 17120 KB Output is partially correct
10 Partially correct 134 ms 18944 KB Output is partially correct
11 Partially correct 135 ms 18444 KB Output is partially correct
12 Partially correct 121 ms 17344 KB Output is partially correct
13 Partially correct 118 ms 18012 KB Output is partially correct
14 Partially correct 119 ms 17796 KB Output is partially correct
15 Partially correct 121 ms 18096 KB Output is partially correct
16 Partially correct 4 ms 860 KB Output is partially correct
17 Correct 78 ms 9952 KB Output is correct
18 Partially correct 116 ms 17360 KB Output is partially correct
19 Partially correct 117 ms 17560 KB Output is partially correct
20 Partially correct 133 ms 18840 KB Output is partially correct
21 Partially correct 136 ms 18656 KB Output is partially correct
22 Partially correct 133 ms 18700 KB Output is partially correct