Submission #966096

#	Time	Username	Problem	Language	Result	Execution time	Memory
966096		anango	Mechanical Doll (IOI18_doll)	C++14	37 / 100	145 ms	19540 KiB

doll

#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 (stderr)

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
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 9 / 18
• Subtask 6: 28 / 56