Submission #966132

#	Time	Username	Problem	Language	Result	Execution time	Memory
966132		anango	Mechanical Doll (IOI18_doll)	C++14	0 / 100	1 ms	348 KiB

doll

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