oj.uz

Submission #1094509

# Submission time Handle Problem Language Result Execution time Memory
1094509 2024-09-29T17:44:37 Z Math4Life2020 Mechanical Doll (IOI18_doll) C++17
10 / 100
 46 ms 4840 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
const int INF = 1e9;

int v2(int x) {
	return __builtin_ctz(x);
}

int l2(int x) {
	return (31-__builtin_clz(x));
}

void print(vector<int> A) {
	cout << "printing\n";
	for (int x: A) {
		cout << x<<" ";
	}
	cout << "\n";
	exit(0);
}

void create_circuit(int M, vector<int> A) {
	int N = A.size();
	vector<int> C;
	C.push_back(A[0]);
	for (int i=0;i<M;i++) {
		C.push_back(-1);
	}
	vector<int> X,Y;
	int CIND = 0;
	int D = l2(2*N-1);
	stack<pii> bd;
	bd.push({N,D});
	while (!bd.empty()) {
		pii p0 = bd.top(); bd.pop();
		int k = p0.first; int d = p0.second;
		if (d<=1) {
			if (k==1) {
				X.push_back(0);
				Y.push_back(-INF);
			} else if (k==2) {
				X.push_back(-INF);
				Y.push_back(-INF);
			} else {
				cout << "reporting error #1\n";
			}
		} else {
			if (k>(1<<(d-1))) {
				Y.push_back(CIND+1);
				X.push_back(CIND+(1<<(d-1)));
				bd.push({k-(1<<(d-1)),d-1});
				bd.push({(1<<(d-1)),d-1});
			} else {
				X.push_back(0);
				Y.push_back(CIND+1);
				bd.push({k,d-1});
			}
		}
		CIND++;
	}

	/*cout << "INIT: print C:\n";
	for (int c: C) {
		cout << c <<" ";
	}
	cout << "\nprint X: \n";
	for (int x: X) {
		cout << x << " ";
	}
	cout << "\nprint Y: \n";
	for (int y: Y) {
		cout << y << " ";
	}*/

	bool st[X.size()];
	bool stn[X.size()];
	for (int t=0;t<N;t++) {
		st[t]=0;
		stn[t]=0;
	}
	for (int t=0;t<N;t++) {
		int cx = 0;
		int locp = -1;
		bool stp = 0;
		while (cx >= 0) {
			if (st[cx]==0) {
				st[cx]=1;
				locp = cx;
				stp = 0;
				cx = X[cx];
			} else {
				st[cx]=0;
				locp = cx;
				stp = 1;
				cx = Y[cx];
			}
		}
		if (cx != -INF) {
			cout << "invalid value\n";
		} else {
			int nval;
			if (t<(N-1)) {
				nval = A[t+1];
			} else {
				nval = 0;
			}
			nval++;
			if (stp==0) {
				X[locp]=-INF+nval;
			} else {
				Y[locp]=-INF+nval;
			}
		}
	}
    for (int d=0;d<X.size();d++) {
		if (X[d]>=0) {
			X[d]=-1-X[d];
		} else {
			X[d]=X[d]-(-INF+1);
		}
		if (Y[d]>=0) {
			Y[d]=-1-Y[d];
		} else {
			Y[d]=Y[d]-(-INF+1);
		}
	}
	/*cout << "print C:\n";
	for (int c: C) {
		cout << c <<" ";
	}
	cout << "\nprint X: \n";
	for (int x: X) {
		cout << x << " ";
	}
	cout << "\nprint Y: \n";
	for (int y: Y) {
		cout << y << " ";
	}
	cout << "\n";*/
	
	//simulate:
	int cpos = 0;
	vector<int> ans;
	int time = 0;
	do {
		time++;
		if (time>(1e6)) {
			cout << "tle\n";
			print(A);
		}
		if (cpos >= 0) {
			if (cpos>0) {
				ans.push_back(cpos);
			}
			cpos = C[cpos];
		} else {
			if (st[-1-cpos]==0) {
				st[-1-cpos]=1;
				cpos = X[-1-cpos];
			} else {
				st[-1-cpos]=0;
				cpos = Y[-1-cpos];
			}
		}
	} while (cpos != 0);
	if (ans.size()!=N) {
		cout << "wrong size!\n";
		print(A);
	} else {
		for (int i=0;i<N;i++) {
			if (ans[i]!=A[i]) {
				cout << "mismatch!\n";
				print(A);
			}
		}
	}
	answer(C,X,Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:117:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |     for (int d=0;d<X.size();d++) {
      |                  ~^~~~~~~~~
doll.cpp:168:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  168 |  if (ans.size()!=N) {
      |      ~~~~~~~~~~^~~
doll.cpp:78:7: warning: variable 'stn' set but not used [-Wunused-but-set-variable]
   78 |  bool stn[X.size()];
      |       ^~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 46 ms 4840 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 46 ms 4840 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
3 Halted 0 ms 0 KB -