oj.uz

Submission #1047434

# Submission time Handle Problem Language Result Execution time Memory
1047434 2024-08-07T12:59:21 Z Tob Mechanical Doll (IOI18_doll) C++14
100 / 100
 66 ms 25480 KB 
#include <bits/stdc++.h>

#include "doll.h"

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;
/*
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 number1");
    }
  }
  for (int j = 1; j <= S; ++j) {
    if (!(-S <= IX[j - 1] && IX[j - 1] <= M)) {
    	cout << IX[j-1] << "\n";
      wrong_answer("wrong serial number2");
    }
    if (!(-S <= IY[j - 1] && IY[j - 1] <= M)) {
      wrong_answer("wrong serial number3");
    }
  }

  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("1\n");
//  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 maxN = (1 << 18);

int n, cnt, ofs;
int a[maxN], sw[maxN];
vector <int> adj[maxN];

int prec(int x, int y, int lo, int hi) {
	if (hi < ofs-n) return 0;
	if (lo == hi) {
		a[lo] = y;
		return 1;
	}
	int mid = (lo + hi) / 2;
	if (x > ofs) exit(1);
	sw[x] ^= 1;
	if (sw[x]) return prec(2*x, y, lo, mid);
	return prec(2*x+1, y, mid+1, hi);
}

int rek(int lo, int hi) {
	if (hi < ofs-n) return -1;
	if (lo == hi) return a[lo];
	int x = ++cnt;
	int mid = (lo + hi) / 2;
	adj[x].pb(rek(lo, mid));
	adj[x].pb(rek(mid+1, hi));
	return -x;
}

void create_circuit(int m, vector <int> b) {
	n = b.size();
	ofs = 1;
	while (ofs < n) ofs *= 2;
	b.pb(0);
	for (int i = 1; i <= n; ) i += prec(1, b[i], 0, ofs-1);
	rek(0, ofs-1);
	vector <int> res1(m+1), res2(cnt), res3(cnt);
	res1[0] = b[0];
	for (int i = 1; i <= m; i++) res1[i] = -min(cnt,1);
	for (int i = 1; i <= cnt; i++) res2[i-1] = adj[i][0], res3[i-1] = adj[i][1];
	answer(res1, res2, res3);
}

//----------------------------------------------------------------------------------
/*
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;
}*/

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 22 ms 12488 KB Output is correct
3 Correct 21 ms 12884 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 6 ms 7772 KB Output is correct
6 Correct 30 ms 16052 KB Output is correct
7 Correct 1 ms 6748 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 22 ms 12488 KB Output is correct
3 Correct 21 ms 12884 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 6 ms 7772 KB Output is correct
6 Correct 30 ms 16052 KB Output is correct
7 Correct 1 ms 6748 KB Output is correct
8 Correct 42 ms 17876 KB Output is correct
9 Correct 40 ms 18504 KB Output is correct
10 Correct 58 ms 25480 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 1 ms 6748 KB Output is correct
13 Correct 1 ms 6748 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 22 ms 12488 KB Output is correct
3 Correct 21 ms 12884 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 6 ms 7772 KB Output is correct
6 Correct 30 ms 16052 KB Output is correct
7 Correct 1 ms 6748 KB Output is correct
8 Correct 42 ms 17876 KB Output is correct
9 Correct 40 ms 18504 KB Output is correct
10 Correct 58 ms 25480 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 1 ms 6748 KB Output is correct
13 Correct 1 ms 6748 KB Output is correct
14 Correct 57 ms 24904 KB Output is correct
15 Correct 37 ms 18512 KB Output is correct
16 Correct 61 ms 24628 KB Output is correct
17 Correct 1 ms 6744 KB Output is correct
18 Correct 1 ms 6744 KB Output is correct
19 Correct 1 ms 6748 KB Output is correct
20 Correct 56 ms 25064 KB Output is correct
21 Correct 1 ms 6744 KB Output is correct
22 Correct 1 ms 6748 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 1 ms 6744 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 1 ms 6760 KB Output is correct
7 Correct 1 ms 6780 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 34 ms 16336 KB Output is correct
3 Correct 38 ms 16448 KB Output is correct
4 Correct 53 ms 23088 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 34 ms 16336 KB Output is correct
3 Correct 38 ms 16448 KB Output is correct
4 Correct 53 ms 23088 KB Output is correct
5 Correct 58 ms 24468 KB Output is correct
6 Correct 55 ms 24368 KB Output is correct
7 Correct 55 ms 24256 KB Output is correct
8 Correct 66 ms 23892 KB Output is correct
9 Correct 36 ms 17320 KB Output is correct
10 Correct 57 ms 23784 KB Output is correct
11 Correct 53 ms 23556 KB Output is correct
12 Correct 38 ms 17736 KB Output is correct
13 Correct 36 ms 18016 KB Output is correct
14 Correct 39 ms 18252 KB Output is correct
15 Correct 45 ms 18248 KB Output is correct
16 Correct 2 ms 7004 KB Output is correct
17 Correct 35 ms 17548 KB Output is correct
18 Correct 36 ms 17480 KB Output is correct
19 Correct 35 ms 17736 KB Output is correct
20 Correct 56 ms 23760 KB Output is correct
21 Correct 54 ms 23604 KB Output is correct
22 Correct 55 ms 23544 KB Output is correct