oj.uz

답안 #1045106

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1045106 2024-08-05T16:52:51 Z n1k 자동 인형 (IOI18_doll) C++17
2 / 100
 40 ms 17596 KB 
#include <bits/stdc++.h>
#include "doll.h"
//#include "debug.cpp"

#define debug(...) 0

using namespace std;

vector<int> x, y, c, state, order;
vector<array<int, 2>> in;
int t = 0;

int tree(vector<int> nodes){
    // nodes.size() must be a power of 2
    // returns id of exit node
    while(nodes.size()>1){
        vector<int> nnodes;
        for(int i=0; i<nodes.size(); i+=2){
            x.push_back(nodes[i]);
            y.push_back(nodes[i+1]);
            state.push_back(0);

            nnodes.push_back(-x.size());
            if(nodes[i]>=0){
                in[nodes[i]]={-int(x.size()), 0};
            }
            if(nodes[i+1]>=0){
                in[nodes[i+1]]={-int(x.size()), 1};
            }
        }
        swap(nodes, nnodes);
    }
    return nodes.front();
}

void sim(int u){
    if(u>=0){
        if(order[u]!=-1){
            return;
        }
        order[u]=t++;
        sim(c[u]);
    }else{
        u = -u-1;
        if(state[u]==0){
            state[u]^=1;
            sim(x[u]);
        }else{
            state[u]^=1;
            sim(y[u]);
        }
    }
}

void create_circuit(int M, std::vector<int> A) {
    int n = A.size(), now = 1;
    vector<int> roots(20);
    in.assign(n+1, {});
    for(int i=0; i<20; i++){
        if(n&(1<<i)){
            vector<int> nodes(1<<i);
            iota(nodes.begin(), nodes.end(), now);
            roots[i]=tree(nodes);
            now += 1<<i;
        }
    }


    // make switcher
    int len = log2(n) + 1;
    int start = -x.size()-1;
    for(int i=0; i<len; i++){
        if(roots[len - i - 1]){
            x.push_back(roots[len - i - 1]);
            y.push_back(-x.size() - 1);
            state.push_back(0);
            if(roots[len - i - 1]>=0){
                in[roots[len - i - 1]] = {-int(x.size()), 0};
            }
        }else{
            x.push_back(start);
            y.push_back(-x.size() - 1);
            state.push_back(0);
     
        }
    }
    c.assign(M+1, start);
    order.assign(n+1, -1);
    y.back() = 0;
    c[0]=start;
    vector<array<int, 2>> rev(n+1);

    sim(start);
    for(int i=0; i<order.size(); i++){
        rev[order[i]] = in[i];
    }
    debug(order);
    debug(c);
    debug(x);
    debug(y);
    debug(in);
    debug(rev);

    for(int i=0; i<n; i++){
        auto [module, side] = rev[i];
        module = -module - 1;
        if(side==0){
            x[module] = A[i];
        }else{
            y[module] = A[i];
        }
    }

    debug(c);
    debug(x);
    debug(y);

    answer(c, x, y);
}

Compilation message

doll.cpp: In function 'int tree(std::vector<int>)':
doll.cpp:18:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         for(int i=0; i<nodes.size(); i+=2){
      |                      ~^~~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:94:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for(int i=0; i<order.size(); i++){
      |                  ~^~~~~~~~~~~~~
doll.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 0
      |                    ^
doll.cpp:97:5: note: in expansion of macro 'debug'
   97 |     debug(order);
      |     ^~~~~
doll.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 0
      |                    ^
doll.cpp:98:5: note: in expansion of macro 'debug'
   98 |     debug(c);
      |     ^~~~~
doll.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 0
      |                    ^
doll.cpp:99:5: note: in expansion of macro 'debug'
   99 |     debug(x);
      |     ^~~~~
doll.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 0
      |                    ^
doll.cpp:100:5: note: in expansion of macro 'debug'
  100 |     debug(y);
      |     ^~~~~
doll.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 0
      |                    ^
doll.cpp:101:5: note: in expansion of macro 'debug'
  101 |     debug(in);
      |     ^~~~~
doll.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 0
      |                    ^
doll.cpp:102:5: note: in expansion of macro 'debug'
  102 |     debug(rev);
      |     ^~~~~
doll.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 0
      |                    ^
doll.cpp:114:5: note: in expansion of macro 'debug'
  114 |     debug(c);
      |     ^~~~~
doll.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 0
      |                    ^
doll.cpp:115:5: note: in expansion of macro 'debug'
  115 |     debug(x);
      |     ^~~~~
doll.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 0
      |                    ^
doll.cpp:116:5: note: in expansion of macro 'debug'
  116 |     debug(y);
      |     ^~~~~

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 26 ms 5836 KB Output is correct
3 Correct 26 ms 5436 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 6 ms 1488 KB Output is correct
6 Correct 40 ms 7176 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 26 ms 5836 KB Output is correct
3 Correct 26 ms 5436 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 6 ms 1488 KB Output is correct
6 Correct 40 ms 7176 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Runtime error 17 ms 17596 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 26 ms 5836 KB Output is correct
3 Correct 26 ms 5436 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 6 ms 1488 KB Output is correct
6 Correct 40 ms 7176 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Runtime error 17 ms 17596 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -