oj.uz

답안 #284726

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
284726 2020-08-27T23:09:52 Z peti1234 자동 인형 (IOI18_doll) C++17
100 / 100
 171 ms 11860 KB 
#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
const int c=270002;
int n, po=1, db, sw, el[c], pos, cnt;
vector<int> s, x, y, sz;
bool v[c], akt[c];
void dfs(int a, int x) {
    if (a>=po) return;
    if (db-n>=x) {db-=x, sw-=x-1, v[a]=1; return;}
    dfs(2*a, x/2), dfs(2*a+1, x/2);
}
void dfs2(int a) {
    if (a>=po) return;
    if (v[a]) {el[a]=1; return;}
    cnt++, el[a]=cnt;
    if (a<po/2) {
        dfs2(2*a), x[el[a]-1]=-el[2*a];
        dfs2(2*a+1), y[el[a]-1]=-el[2*a+1];
    }
}
void dfs3(int a) {
    if (v[a]) return;
    if (a<po/2) {
        dfs3(2*a+akt[a]);
        akt[a]=!akt[a];
    } else {
        //cout << a << " " << el[a]-1 << " " << cnt << " " << sz[cnt] << endl;
        if (!akt[a]) x[el[a]-1]=sz[cnt];
        else y[el[a]-1]=sz[cnt];
        cnt++, akt[a]=!akt[a];
    }
}
void create_circuit(int m, vector<int> p) {
    for (int i=0; i<m+1; i++) s.push_back(-1);
    sz=p, n=sz.size();
    if (n%2==0) sz.push_back(-1);
    sz.push_back(0), n=sz.size();
    while(po<n) po*=2; db=po, sw=po-1;
    dfs(1, po);
    x.resize(sw), y.resize(sw);
    dfs2(1), cnt=0;
    for (int i=0; i<po; i++) dfs3(1);
    /*for (int i=0; i<sw; i++) {
        cout << x[i] << " " << y[i] << "\n";
    }*/
    answer(s, x, y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:39:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   39 |     while(po<n) po*=2; db=po, sw=po-1;
      |     ^~~~~
doll.cpp:39:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   39 |     while(po<n) po*=2; db=po, sw=po-1;
      |                        ^~

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 53 ms 4564 KB Output is correct
3 Correct 45 ms 4432 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1604 KB Output is correct
6 Correct 68 ms 6688 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 53 ms 4564 KB Output is correct
3 Correct 45 ms 4432 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1604 KB Output is correct
6 Correct 68 ms 6688 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 95 ms 7728 KB Output is correct
9 Correct 124 ms 8216 KB Output is correct
10 Correct 134 ms 11860 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 53 ms 4564 KB Output is correct
3 Correct 45 ms 4432 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1604 KB Output is correct
6 Correct 68 ms 6688 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 95 ms 7728 KB Output is correct
9 Correct 124 ms 8216 KB Output is correct
10 Correct 134 ms 11860 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 141 ms 11164 KB Output is correct
15 Correct 101 ms 7224 KB Output is correct
16 Correct 146 ms 10912 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 143 ms 11416 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #5
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 90 ms 6312 KB Output is correct
3 Correct 77 ms 6280 KB Output is correct
4 Correct 115 ms 9512 KB Output is correct

Subtask #6
56.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 90 ms 6312 KB Output is correct
3 Correct 77 ms 6280 KB Output is correct
4 Correct 115 ms 9512 KB Output is correct
5 Correct 171 ms 10796 KB Output is correct
6 Correct 118 ms 10508 KB Output is correct
7 Correct 117 ms 10616 KB Output is correct
8 Correct 111 ms 10280 KB Output is correct
9 Correct 80 ms 6324 KB Output is correct
10 Correct 125 ms 10220 KB Output is correct
11 Correct 131 ms 9864 KB Output is correct
12 Correct 83 ms 6588 KB Output is correct
13 Correct 81 ms 6912 KB Output is correct
14 Correct 89 ms 6972 KB Output is correct
15 Correct 79 ms 7172 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 92 ms 6400 KB Output is correct
18 Correct 85 ms 6448 KB Output is correct
19 Correct 100 ms 6588 KB Output is correct
20 Correct 147 ms 10152 KB Output is correct
21 Correct 111 ms 9768 KB Output is correct
22 Correct 136 ms 9872 KB Output is correct