oj.uz

Submission #785971

# Submission time Handle Problem Language Result Execution time Memory
785971 2023-07-17T20:52:46 Z esomer Mechanical Doll (IOI18_doll) C++17
100 / 100
 318 ms 57256 KB 
#include<bits/stdc++.h>
#include "doll.h"

using namespace std;

typedef long long ll;

vector<int> X, Y;
vector<set<int>> which;
map<int, int> mp;
vector<int> vis;

int id;

void DFS(int curr, int add, vector<int>& adj, int org){
	if(add >= (int)adj.size()){
		if(id < (int)adj.size()){
			id++; 
			vis.push_back(curr);
		}
		return;
	}
	int ind = (int)X.size();
	DFS(curr + add, add * 2, adj, org);
	DFS(curr, add * 2, adj, org);
}

int DFS2(int curr, int add, vector<int>& adj, int org){
	if(add >= (int)adj.size()){
		bool gd = mp.count(curr);
		if(gd) return mp[curr];
		else return org;
	}
	int ind = (int)X.size();
	X.push_back(-1);
	Y.push_back(-1);
	which.push_back({});
	if(org == 0) org = -(ind+1);
	Y[ind] = DFS2(curr + add, add * 2, adj, org);
	X[ind] = DFS2(curr, add * 2, adj, org);
	if(X[ind] >= 0 || X[ind] == org) which[ind].insert(X[ind]);
	else{
		int t = 0;
		for(auto x : which[-X[ind] - 1]){
			if(t == 2) break;
			t++;
			which[ind].insert(x);
		}
	}
	if(Y[ind] >= 0 || Y[ind] == org) which[ind].insert(Y[ind]);
	else{
		int t = 0;
		for(auto x : which[-Y[ind] - 1]){
			if(t == 2) break;
			t++;
			which[ind].insert(x);
		}
	}
	if((int)which[ind].size() == 1){
		X.pop_back();
		Y.pop_back();
		int val = *which[ind].begin();
		which.pop_back();
		return val;
	}
	return -(ind+1);
}

void create_circuit(int M, vector<int> A){
	int m = M;
	int n = (int)A.size();
	if(n == 1){
		vector<int> c(m+1, 0);
		c[0] = A[0];
		answer(c, X, Y);
		return;
	}
	vector<int> c(m+1, -2);
	A.push_back(0);
	c[0] = A[0];
	vector<int> adj;
	for(int i = 0; i < n; i++){
		adj.push_back(A[i+1]);
		c[A[i]] = -1;
	}
	for(int i = 1; i <= m; i++){
		if(c[i] == -2) c[i] = i;
	}
	id = 0;
	mp.clear();
	vis.clear();
	DFS(0, 1, adj, 0);
	sort(vis.begin(), vis.end());
	for(int j = 0; j < (int)vis.size(); j++){
		mp[vis[j]] = adj[j];
	}
	DFS2(0, 1, adj, 0);
	answer(c, X, Y);
}

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

Compilation message

doll.cpp: In function 'void DFS(int, int, std::vector<int>&, int)':
doll.cpp:23:6: warning: unused variable 'ind' [-Wunused-variable]
   23 |  int ind = (int)X.size();
      |      ^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 79 ms 20024 KB Output is correct
3 Correct 96 ms 21152 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1364 KB Output is correct
6 Correct 129 ms 29196 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 79 ms 20024 KB Output is correct
3 Correct 96 ms 21152 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1364 KB Output is correct
6 Correct 129 ms 29196 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 144 ms 38100 KB Output is correct
9 Correct 200 ms 41732 KB Output is correct
10 Correct 283 ms 57256 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 79 ms 20024 KB Output is correct
3 Correct 96 ms 21152 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1364 KB Output is correct
6 Correct 129 ms 29196 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 144 ms 38100 KB Output is correct
9 Correct 200 ms 41732 KB Output is correct
10 Correct 283 ms 57256 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 292 ms 56848 KB Output is correct
15 Correct 194 ms 41504 KB Output is correct
16 Correct 305 ms 56644 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 281 ms 56972 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 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 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 73 ms 8512 KB Output is correct
3 Correct 105 ms 8516 KB Output is correct
4 Correct 192 ms 12848 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 73 ms 8512 KB Output is correct
3 Correct 105 ms 8516 KB Output is correct
4 Correct 192 ms 12848 KB Output is correct
5 Correct 315 ms 56600 KB Output is correct
6 Correct 318 ms 56444 KB Output is correct
7 Correct 280 ms 56472 KB Output is correct
8 Correct 306 ms 56228 KB Output is correct
9 Correct 157 ms 23988 KB Output is correct
10 Correct 256 ms 48896 KB Output is correct
11 Correct 300 ms 55588 KB Output is correct
12 Correct 169 ms 36484 KB Output is correct
13 Correct 140 ms 37464 KB Output is correct
14 Correct 182 ms 41396 KB Output is correct
15 Correct 180 ms 41468 KB Output is correct
16 Correct 4 ms 1364 KB Output is correct
17 Correct 140 ms 37064 KB Output is correct
18 Correct 148 ms 36836 KB Output is correct
19 Correct 176 ms 36496 KB Output is correct
20 Correct 277 ms 55880 KB Output is correct
21 Correct 276 ms 55424 KB Output is correct
22 Correct 271 ms 55712 KB Output is correct