oj.uz

Submission #785966

# Submission time Handle Problem Language Result Execution time Memory
785966 2023-07-17T20:44:40 Z esomer Mechanical Doll (IOI18_doll) C++17
84 / 100
 315 ms 56548 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();
	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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 75 ms 19972 KB Output is correct
3 Correct 86 ms 21060 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1364 KB Output is correct
6 Correct 148 ms 29196 KB Output is correct
7 Incorrect 0 ms 212 KB wrong serial number
8 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 75 ms 19972 KB Output is correct
3 Correct 86 ms 21060 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1364 KB Output is correct
6 Correct 148 ms 29196 KB Output is correct
7 Incorrect 0 ms 212 KB wrong serial number
8 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 75 ms 19972 KB Output is correct
3 Correct 86 ms 21060 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1364 KB Output is correct
6 Correct 148 ms 29196 KB Output is correct
7 Incorrect 0 ms 212 KB wrong serial number
8 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 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 1 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 74 ms 8508 KB Output is correct
3 Correct 121 ms 8528 KB Output is correct
4 Correct 176 ms 12836 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 74 ms 8508 KB Output is correct
3 Correct 121 ms 8528 KB Output is correct
4 Correct 176 ms 12836 KB Output is correct
5 Correct 299 ms 56544 KB Output is correct
6 Correct 297 ms 56440 KB Output is correct
7 Correct 306 ms 56548 KB Output is correct
8 Correct 302 ms 56140 KB Output is correct
9 Correct 147 ms 23988 KB Output is correct
10 Correct 262 ms 48988 KB Output is correct
11 Correct 304 ms 55480 KB Output is correct
12 Correct 174 ms 36464 KB Output is correct
13 Correct 142 ms 37492 KB Output is correct
14 Correct 182 ms 41424 KB Output is correct
15 Correct 190 ms 41360 KB Output is correct
16 Correct 4 ms 1436 KB Output is correct
17 Correct 148 ms 37060 KB Output is correct
18 Correct 147 ms 36836 KB Output is correct
19 Correct 183 ms 36412 KB Output is correct
20 Correct 279 ms 55932 KB Output is correct
21 Correct 281 ms 55512 KB Output is correct
22 Correct 315 ms 55668 KB Output is correct