oj.uz

Submission #785880

# Submission time Handle Problem Language Result Execution time Memory
785880 2023-07-17T17:37:24 Z esomer Mechanical Doll (IOI18_doll) C++17
6 / 100
 195 ms 64344 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;

int 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 adj[id - 1];
		}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] = DFS(curr + add, add * 2, adj, org);
	X[ind] = DFS(curr, add * 2, adj, org);
	return -(ind+1);
}

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);
	//~ cout << "ind " << ind << endl;
	if(X[ind] >= 0 || X[ind] == org) which[ind].insert(X[ind]);
	else{
		//~ cout << "X[ind] " << X[ind] << endl;
		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{
		//~ cout << "Y[ind] " << Y[ind] << endl;
		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, -1);
	A.push_back(0);
	c[0] = A[0];
	vector<vector<int>> adj(M + 1);
	for(int i = 0; i < n; i++){
		adj[A[i]].push_back(A[i+1]);
	}
	for(int i = 1; i <= M; i++){
		if((int)adj[i].size() == 0){
			c[i] = i;
			continue;
		}
		id = 0;
		mp.clear();
		vis.clear();
		c[i] = DFS(0, 1, adj[i], 0);
		sort(vis.begin(), vis.end());
		for(int j = 0; j < (int)vis.size(); j++){
			mp[vis[j]] = adj[i][j];
		}
		c[i] = DFS2(0, 1, adj[i], 0);
	}
	//~ for(int i = 0; i <= m; i++){
		//~ cout << "i " << i << " c " << c[i] << endl;
	//~ }
	//~ for(int i = 0; i < (int)X.size(); i++){
		//~ cout << "s " << -(i+1) << " x " << X[i] << " y " << Y[i] << endl;
	//~ }
	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;
//}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 23 ms 6840 KB Output is correct
3 Correct 26 ms 5604 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 9 ms 3796 KB Output is correct
6 Correct 42 ms 8408 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 23 ms 6840 KB Output is correct
3 Correct 26 ms 5604 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 9 ms 3796 KB Output is correct
6 Correct 42 ms 8408 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 81 ms 22016 KB Output is correct
9 Correct 60 ms 18616 KB Output is correct
10 Correct 114 ms 33424 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 23 ms 6840 KB Output is correct
3 Correct 26 ms 5604 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 9 ms 3796 KB Output is correct
6 Correct 42 ms 8408 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 81 ms 22016 KB Output is correct
9 Correct 60 ms 18616 KB Output is correct
10 Correct 114 ms 33424 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Incorrect 195 ms 64344 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -