oj.uz

Submission #990185

# Submission time Handle Problem Language Result Execution time Memory
990185 2024-05-29T19:59:23 Z Boomyday Mechanical Doll (IOI18_doll) C++17
0 / 100
 116 ms 262144 KB 
//
// Created by adavy on 5/29/2024.
//
#include <bits/stdc++.h>
#include "doll.h"
using namespace std;



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;
    while (n < N) n *= 2;

    vector<int> pat = gen_pattern(n);
    // 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

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

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 728 KB Output is correct
2 Runtime error 116 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 728 KB Output is correct
2 Runtime error 116 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 728 KB Output is correct
2 Runtime error 116 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 113 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 105 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Runtime error 105 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -