oj.uz

Submission #612425

# Submission time Handle Problem Language Result Execution time Memory
612425 2022-07-29T14:53:00 Z neki Mechanical Doll (IOI18_doll) C++14
28 / 100
 96 ms 9696 KB 
#include "doll.h"
#include <bits/stdc++.h>
#define vc vector

using namespace std;

void create_circuit(int m, vc<int> a){
    a.push_back(0);
    int k=a.size();
    while(k != (1<< __builtin_ctz(k))) ++k;
    
    vc<int> c(m+1), x, y;
    c[0]=-1;
    
    int id=1;
    function<int (int, int, vc<int>)> solve=[&](int l, int r, vc<int> arr){
        assert(arr.size());
        
        int mojid=id++;
        x.push_back(INT_MAX), y.push_back(INT_MAX);
        
        int len=(r-l), mid=(l+r)/2;
        int vd=min(len/2, (int)arr.size());
        int vl=arr.size()-vd;assert(vl>=0 and vl<arr.size());
        int pl=len/2-vl, pr=len/2-vd;
        //cout << vd << " " << vl << endl;
        
        vc<int> lev, des;
        for(int i=0, komu=0;i<arr.size();++i){
            if(pl) --pl, des.push_back(arr[i]);
            else{
                if(komu==0) lev.push_back(arr[i]);
                else des.push_back(arr[i]);
                komu= !komu;
            }
        }
        /*cout << mojid << ": "<<endl;
        for(auto v: lev) cout << v <<" "; cout << endl;
        for(auto v: des) cout << v <<" "; cout << endl;*/
        
        assert(len>=2);
        assert(des.size());
        if(len==2){
            if(lev.size()){
                assert(lev.size()==1);
                x[mojid-1]=lev[0];
                if(lev[0]!=0) c[lev[0]]=-1;
            }
            else x[mojid-1]=-1;
            
            if(des.size()){
                assert(des.size()==1);
                y[mojid-1]=des[0];
                if(des[0]!=0) c[des[0]]=-1;
            }
        }
        else{
            if(lev.size()) x[mojid-1]=-solve(l, mid, lev);
            else x[mojid-1]=-1;
            
            y[mojid-1]=-solve(mid, r, des);
        }
        
        return mojid;
    };
    solve(0, k, a);
    
    //for(auto v: c) cout << v << " ";cout << endl;
    //for(auto v: x) cout << v << " ";cout << endl;
    //for(auto v: y) cout << v << " ";cout << endl;
    
    answer(c, x, y);
}

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 lambda function:
doll.cpp:24:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         int vl=arr.size()-vd;assert(vl>=0 and vl<arr.size());
      |                                               ~~^~~~~~~~~~~
doll.cpp:29:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for(int i=0, komu=0;i<arr.size();++i){
      |                             ~^~~~~~~~~~~
doll.cpp:25:26: warning: unused variable 'pr' [-Wunused-variable]
   25 |         int pl=len/2-vl, pr=len/2-vd;
      |                          ^~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 300 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 66 ms 8024 KB Output is correct
3 Correct 59 ms 8048 KB Output is correct
4 Correct 87 ms 9580 KB Output is correct

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 66 ms 8024 KB Output is correct
3 Correct 59 ms 8048 KB Output is correct
4 Correct 87 ms 9580 KB Output is correct
5 Incorrect 96 ms 9696 KB wrong motion
6 Halted 0 ms 0 KB -