Submission #990188

#	Time	Username	Problem	Language	Result	Execution time	Memory
990188		Boomyday	Mechanical Doll (IOI18_doll)	C++17	100 / 100	83 ms	14356 KiB

doll

//
// Created by adavy on 5/29/2024.
//
#include <bits/stdc++.h>
using namespace std;

#include "doll.h"


vector<int> gen_pattern(int n){

    if (n==1) return {0,1};

    vector<int> ans = gen_pattern(n-1);
    int sz = ans.size();
    for (int i=0;i<sz;++i) ans[i] *= 2;
    for(int i=0;i<sz;++i) ans.push_back(ans[i]+1);
    return ans;
}

vector<int> X,Y,AA;
int cur_num = 1;

void update(int lev,vector<int> terms,int& pos){
    X.push_back(0); Y.push_back(0);

    int mypos = pos;


    if (terms.size()==2 && lev==2){
        X[mypos] = terms[0]; Y[mypos] = terms[1]; return;
    }
    else if (terms.size()==1 && lev==2){
        Y[mypos] = terms[0]; X[mypos] = -1; return;
    }

    if (terms.size()<=lev/2){
        Y[mypos] = (-++pos - 1);  X[mypos] = -1;  update(lev/2, terms,pos); return;
    }
    vector<int> left,right;
    for(int i=0;i<terms.size();++i){
        if (i<(terms.size()-lev/2)) left.push_back(terms[i]);
        else right.push_back(terms[i]);
    }
    X[mypos] = (-++pos - 1);  update(lev/2, left,pos);
    Y[mypos] = (-++pos - 1); update(lev/2, right,pos);

}
void create_circuit(int M, std::vector<int> A) {
    A.push_back(0);
    AA = A;
    int N = A.size();

    // get smallest power of 2 geq N
    int n = 1, pat_sz = 0;
    while (n < N){ n *= 2;pat_sz+=1;}


    vector<int> pat = gen_pattern(pat_sz);
    // truncate pattern to size N , left truncate!!!

    reverse(pat.begin(),pat.end()); pat.resize(N); reverse(pat.begin(),pat.end());

    // renumber pattern so it only uses digits from 0 to N-1
    vector<pair<int,int>> to_sort;
    for(int i=0;i<N;++i) to_sort.push_back({pat[i],i});
    sort(to_sort.begin(),to_sort.end());
    for(int i=0;i<N;++i) pat[to_sort[i].second] = i;

    vector<int> C(M+1,-1);
    vector<int> pat2(N);
    for(int i=0;i<N;++i) pat2[i] = A[pat[i]];
    // output pat2

    int pos = 0;



    update(n,pat2,pos);
    // output c x and y


    answer(C,X,Y);



}



/*

int main() {
    grader::M =grader:: read_int();
    grader::N = grader::read_int();
    grader::A.resize(grader::N);
    for (int k = 0; k <grader:: N; ++k) {
        grader::A[k] = grader::read_int();
    }

    grader::answered = false;
    create_circuit(grader::M, grader::A);
    if (!grader::answered) {
        grader::wrong_answer("answered not exactly once");
    }
    FILE *file_out = fopen("out.txt", "w");
    fprintf(file_out, "%d\n", grader::S);
    for (int i = 0; i <= grader::M; ++i) {
        fprintf(file_out, "%d\n", grader::IC[i]);
    }
    for (int j = 1; j <= grader::S; ++j) {
        fprintf(file_out, "%d %d\n", grader::IX[j - 1], grader::IY[j - 1]);
    }
    fclose(file_out);
    grader::simulate();
    return 0;
}
*/

Compilation message (stderr)

doll.cpp: In function 'void update(int, std::vector<int>, int&)':
doll.cpp:37:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |     if (terms.size()<=lev/2){
      |         ~~~~~~~~~~~~^~~~~~~
doll.cpp:41:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i=0;i<terms.size();++i){
      |                 ~^~~~~~~~~~~~~
doll.cpp:42:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         if (i<(terms.size()-lev/2)) left.push_back(terms[i]);
      |             ~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56