oj.uz

Submission #283407

# Submission time Handle Problem Language Result Execution time Memory
283407 2020-08-25T16:33:38 Z Mercenary Mechanical Doll (IOI18_doll) C++14
100 / 100
 153 ms 11676 KB 
#include<bits/stdc++.h>
#include "doll.h"
#define pb push_back
using namespace std;
const int maxn = 3e5 + 5;
int n , m , sz;
int nTime = 1;
int a[maxn] , b[maxn];

void build(int x , int l , int r , int sz){
    int mid = l + r >> 1;
    if(l + 1 == r){
        if(sz <= mid)a[x] = 1;
        return;
    }
    b[x] = ++nTime;
    build(b[x] , l , mid , sz);
    if(sz > mid){
        a[x] = ++nTime;
        build(a[x] , mid + 1 , r , sz);
    }else{
        a[x] = 1;
    }
}

bool vis[maxn];
void dfs(int u , int val){
    vis[u] ^= 1;
    int & res = (vis[u] ? a[u] : b[u]);
    if(res)dfs(res , val);
    else res = val;
}

void create_circuit(int M, std::vector<int> A) {
    A.pb(0);
    int p = 1;
    while(p * 2 <= (int)A.size() - 2)p <<= 1;
    build(1 , 1 , p * 2 , (int)A.size() - 1);
    for(int i = 1 ; i < A.size() ; ++i)dfs(1 , -A[i]);
    vector<int> X(nTime) , Y(nTime) , C(M + 1 , -1);
    C[0] = A[0];
    for(int i = 0 ; i < nTime ; ++i)X[i] = -a[i + 1] , Y[i] = -b[i + 1];
    answer(C, X, Y);
}

#ifdef LOCAL
#include <cstdio>
#include <cstdlib>
#include "doll.h"

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);
    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;
}

int main() {
  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;
}

#endif // LOCAL

Compilation message

doll.cpp: In function 'void build(int, int, int, int)':
doll.cpp:11:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   11 |     int mid = l + r >> 1;
      |               ~~^~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:39:23: 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 = 1 ; i < A.size() ; ++i)dfs(1 , -A[i]);
      |                     ~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 47 ms 4260 KB Output is correct
3 Correct 48 ms 4352 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 1484 KB Output is correct
6 Correct 64 ms 6668 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 47 ms 4260 KB Output is correct
3 Correct 48 ms 4352 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 1484 KB Output is correct
6 Correct 64 ms 6668 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 81 ms 7612 KB Output is correct
9 Correct 87 ms 8276 KB Output is correct
10 Correct 140 ms 11676 KB Output is correct
11 Correct 1 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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 47 ms 4260 KB Output is correct
3 Correct 48 ms 4352 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 1484 KB Output is correct
6 Correct 64 ms 6668 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 81 ms 7612 KB Output is correct
9 Correct 87 ms 8276 KB Output is correct
10 Correct 140 ms 11676 KB Output is correct
11 Correct 1 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 11092 KB Output is correct
15 Correct 80 ms 7144 KB Output is correct
16 Correct 125 ms 10828 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 148 ms 11288 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 79 ms 6192 KB Output is correct
3 Correct 74 ms 6136 KB Output is correct
4 Correct 153 ms 9372 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 79 ms 6192 KB Output is correct
3 Correct 74 ms 6136 KB Output is correct
4 Correct 153 ms 9372 KB Output is correct
5 Correct 150 ms 10656 KB Output is correct
6 Correct 123 ms 10392 KB Output is correct
7 Correct 117 ms 10512 KB Output is correct
8 Correct 118 ms 10180 KB Output is correct
9 Correct 83 ms 6192 KB Output is correct
10 Correct 118 ms 10008 KB Output is correct
11 Correct 118 ms 9752 KB Output is correct
12 Correct 71 ms 6392 KB Output is correct
13 Correct 72 ms 6840 KB Output is correct
14 Correct 79 ms 6964 KB Output is correct
15 Correct 76 ms 7084 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 78 ms 6444 KB Output is correct
18 Correct 72 ms 6448 KB Output is correct
19 Correct 82 ms 6424 KB Output is correct
20 Correct 115 ms 10008 KB Output is correct
21 Correct 135 ms 9732 KB Output is correct
22 Correct 111 ms 9752 KB Output is correct