oj.uz

Submission #568087

# Submission time Handle Problem Language Result Execution time Memory
568087 2022-05-24T16:04:18 Z hoanghq2004 Mechanical Doll (IOI18_doll) C++14
100 / 100
 129 ms 11736 KB 
#include <bits/stdc++.h>
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "doll.h"

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

//namespace {
//
//constexpr int P_MAX = 20000000;
//constexpr int S_MAX = 400000;
//
//int M, N;
//std::vector<int> A;
//
//bool answered;
//int S;
//std::vector<int> IC, IX, IY;
//
//int read_int() {
//  int x;
//  if (scanf("%d", &x) != 1) {
//    fprintf(stderr, "Error while reading input\n");
//    exit(1);
//  }
//  return x;
//}
//
//void wrong_answer(const char *MSG) {
//  printf("Wrong Answer: %s\n", MSG);
//  exit(0);
//}
//
//void simulate() {
//  if (S > S_MAX) {
//    char str[50];
//    sprintf(str, "over %d switches", S_MAX);
//    wrong_answer(str);
//  }
//  for (int i = 0; i <= M; ++i) {
//    if (!(-S <= IC[i] && IC[i] <= M)) {
//      wrong_answer("wrong serial number");
//    }
//  }
//  for (int j = 1; j <= S; ++j) {
//    if (!(-S <= IX[j - 1] && IX[j - 1] <= M)) {
//      wrong_answer("wrong serial number");
//    }
//    if (!(-S <= IY[j - 1] && IY[j - 1] <= M)) {
//      wrong_answer("wrong serial number");
//    }
//  }
//
//  int P = 0;
//  std::vector<bool> state(S + 1, false);
//  int pos = IC[0];
//  int k = 0;
//  FILE *file_log = fopen("log.txt", "w");
//  fprintf(file_log, "0\n");
//  for (;;) {
//    fprintf(file_log, "%d\n", pos);
////    cout << pos << ' ';
//    if (pos < 0) {
//      if (++P > P_MAX) {
//        fclose(file_log);
//        char str[50];
//        sprintf(str, "over %d inversions", P_MAX);
//        wrong_answer(str);
//      }
//      state[-pos] = !state[-pos];
//      pos = state[-pos] ? IX[-(1 + pos)] : IY[-(1 + pos)];
//    } else {
//      if (pos == 0) {
//        break;
//      }
//      if (k >= N) {
//        fclose(file_log);
//        wrong_answer("wrong motion");
//      }
//      if (pos != A[k++]) {
//        fclose(file_log);
//        wrong_answer("wrong motion");
//      }
//      pos = IC[pos];
//    }
//  }
//  fclose(file_log);
//  if (k != N) {
//    wrong_answer("wrong motion");
//  }
//  for (int j = 1; j <= S; ++j) {
//    if (state[j]) {
//      wrong_answer("state 'Y'");
//    }
//  }
//  printf("Accepted: %d %d\n", S, P);
//}
//
//}  // namespace
//
//void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y) {
//  if (answered) {
//    wrong_answer("answered not exactly once");
//  }
//  answered = true;
//  // check if input format is correct
//  if ((int)C.size() != M + 1) {
//    wrong_answer("wrong array length");
//  }
//  if (X.size() != Y.size()) {
//    wrong_answer("wrong array length");
//  }
//  S = X.size();
//  IC = C;
//  IX = X;
//  IY = Y;
//}

const int Nm = 4e5 + 10;

int cnt;
int x[Nm], y[Nm];

int build(int L, int R, int k, int n) {
    if (L == R) return 1e9; // leaf
    int cur = ++cnt;
    int mid = L + R >> 1;
    if (n >> k & 1) {
        x[cur] = build(L, mid, k - 1, n);
        y[cur] = build(mid + 1, R, k - 1, (1 << k) - 1);
    } else {
        x[cur] = 1;
        y[cur] = build(L, mid, k - 1, n);
    }
    return cur;
}

int Flip[Nm];

void add(int u, int val) {
    assert(u >= 0);
    Flip[u] ^= 1;
    if (Flip[u]) {
        if (x[u] == 1e9) {
            x[u] = - val;
            return;
        }
        add(x[u], val);
    } else {
        if (y[u] == 1e9) {
            y[u] = - val;
            return;
        }
        add(y[u], val);
    }
}

void create_circuit(int M, std::vector<int> A) {
    vector<int> C(M + 1);
    A.push_back(0);
    int N = A.size();
    int m = 0;
    while ((1 << m) < N) ++m;
    build(0, (1 << m) - 1, m - 1, N - 1);
//    build(N);
//    cout << cnt << '\n';
//assert(0);
    for (int i = 0; i < N; ++i) add(1, A[i]);
//    for (int i = 1; i <= cnt; ++i) cout << x[i] << ' ' << y[i] << '\n';
//    exit(0);

    for (int i = 0; i <= M; ++i) C[i] = -1;
    vector <int> X, Y;
    for (int i = 1; i <= cnt; ++i) X.push_back(- x[i]), Y.push_back(- y[i]);
//    cout << X.size() << ' ' << Y.size() << '\n';
    answer(C, X, Y);
}
//
//int main() {
////    freopen("test.inp", "r", stdin);
//  M = read_int();
//  N = read_int();
//  A.resize(N);
//  for (int k = 0; k < N; ++k) {
//    A[k] = read_int();
//  }
//
//  answered = false;
//  create_circuit(M, A);
//  if (!answered) {
//    wrong_answer("answered not exactly once");
//  }
//  FILE *file_out = fopen("out.txt", "w");
//  fprintf(file_out, "%d\n", S);
//  for (int i = 0; i <= M; ++i) {
//    fprintf(file_out, "%d\n", IC[i]);
//  }
//  for (int j = 1; j <= S; ++j) {
//    fprintf(file_out, "%d %d\n", IX[j - 1], IY[j - 1]);
//  }
//  fclose(file_out);
//  simulate();
//  return 0;
//}

Compilation message

doll.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
doll.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
doll.cpp: In function 'int build(int, int, int, int)':
doll.cpp:133:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  133 |     int mid = L + R >> 1;
      |               ~~^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 42 ms 5020 KB Output is correct
3 Correct 37 ms 4764 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 9 ms 1492 KB Output is correct
6 Correct 58 ms 6956 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 42 ms 5020 KB Output is correct
3 Correct 37 ms 4764 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 9 ms 1492 KB Output is correct
6 Correct 58 ms 6956 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 87 ms 7700 KB Output is correct
9 Correct 72 ms 8052 KB Output is correct
10 Correct 109 ms 11736 KB Output is correct
11 Correct 1 ms 312 KB Output is correct
12 Correct 1 ms 304 KB Output is correct
13 Correct 1 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 42 ms 5020 KB Output is correct
3 Correct 37 ms 4764 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 9 ms 1492 KB Output is correct
6 Correct 58 ms 6956 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 87 ms 7700 KB Output is correct
9 Correct 72 ms 8052 KB Output is correct
10 Correct 109 ms 11736 KB Output is correct
11 Correct 1 ms 312 KB Output is correct
12 Correct 1 ms 304 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 114 ms 11384 KB Output is correct
15 Correct 68 ms 7284 KB Output is correct
16 Correct 129 ms 11140 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 107 ms 11520 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 69 ms 6808 KB Output is correct
3 Correct 74 ms 6864 KB Output is correct
4 Correct 95 ms 10252 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 69 ms 6808 KB Output is correct
3 Correct 74 ms 6864 KB Output is correct
4 Correct 95 ms 10252 KB Output is correct
5 Correct 105 ms 10980 KB Output is correct
6 Correct 100 ms 10840 KB Output is correct
7 Correct 112 ms 10924 KB Output is correct
8 Correct 96 ms 10616 KB Output is correct
9 Correct 69 ms 6776 KB Output is correct
10 Correct 109 ms 10484 KB Output is correct
11 Correct 98 ms 10300 KB Output is correct
12 Correct 64 ms 6820 KB Output is correct
13 Correct 73 ms 7204 KB Output is correct
14 Correct 69 ms 7248 KB Output is correct
15 Correct 70 ms 7356 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 65 ms 8092 KB Output is correct
18 Correct 68 ms 6904 KB Output is correct
19 Correct 62 ms 6812 KB Output is correct
20 Correct 104 ms 10460 KB Output is correct
21 Correct 123 ms 10280 KB Output is correct
22 Correct 94 ms 10244 KB Output is correct