oj.uz

Submission #135528

# Submission time Handle Problem Language Result Execution time Memory
135528 2019-07-24T07:35:53 Z Adhyyan1252 Mechanical Doll (IOI18_doll) C++11
100 / 100
 112 ms 14728 KB 
#include "doll.h"
#include <bits/stdc++.h>

using namespace std;
#define cout if(false) cout
#define INF 1e7
vector<int> t, a;

int n; 
int tot;
void genTree(int i, int s, int e){
	if(s == e){
		t[i] = INF; //symbol for non-device
		return;
	}
	t[i] = 0;
	int m = (s + e)/2;
	if(tot - (m-s+1) >= n){ //can prune this off
		tot -= (m-s+1);
		t[i*2] = INF+1; //symbol for return to start of tree
	}else{
		genTree(i*2, s, m);
	}
	genTree(i*2+1, m+1, e);
}

int num = -1, cnt = 0;

void giveNames(int i, int s, int e){

	if(t[i] == INF){ //this has to be return 
		return;
	}else if(t[i] == INF+1){
		t[i] = -1; // returns to origin
		return;
	}

	t[i] = num;
	num--;
	int m = (s + e)/2;
	giveNames(i*2, s, m);
	giveNames(i*2+1, m+1, e);
}

vector<int> states;
void sim(int i, int cnt){
	//cout<<"SIMUL: "<<i<<" "<<cnt<<endl;
	if(t[i] == INF){
		t[i] = cnt;
		return;
	}else if(i != 1 && t[i] == -1){ //means do nothing
		sim(1, cnt);
		return;
	}

	if(states[i] == 0){
		states[i] ^= 1;
		sim(i*2, cnt);
	}else{
		states[i] ^= 1;
		sim(i*2+1, cnt);
	}
}


void create_circuit(int M, std::vector<int> A) {
	n = A.size()+1;
	a = A;
	a.push_back(0);
	//generate next power of two
	tot = 1<<((int)(ceil(log2(n))));
	t = vector<int>(tot*2+1, -INF);
	cout<<"STARTED GEN"<<endl;
	genTree(1, 0, tot-1);
	cout<<"Gen"<<endl;
	giveNames(1, 0, tot-1);
	cout<<"Names"<<endl;
	for(int i = 0; i < t.size(); i++){
		cout<<i<<" "<<t[i]<<endl;
	}
	states = vector<int>(t.size());
	for(int i = 0; i < n; i++){
		// /cout<<"SIM "<<i<<endl;
		sim(1, a[i]);
	}
	cout<<"SIMMED"<<endl;
	for(int i = 0; i < states.size(); i++){
		assert(states[i] == 0);
	}

	//so its done numbering. now need to output it
	vector<int> C(M+1, -1);
	int s = -num - 1;
	vector<int> X(s), Y(s);
	for(int i = 0; i < t.size(); i++){
		if((t[i] == INF) || t[i] == INF+1 || t[i] < -s-1 || (i != 1 && t[i] == -1) || t[i] >= 0) continue;
		cout<<i<<" "<<t[i]<<endl;
		X[-t[i]-1] = t[i*2];
		Y[-t[i]-1] = t[i*2+1];
	}
	cout<<"ANSWERING "<<endl;
	for(int i = 0; i< C.size(); i++){
		cout<<i<<" "<<C[i]<<endl;
	}
	for(int i = 0; i < X.size(); i++){
		cout<<i<<" : "<<-i-1<<" : "<<X[i]<<" "<<Y[i]<<endl;
	}
	answer(C, X, Y);
	cout<<"DONE"<<endl;
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:78:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for(int i = 0; i < t.size(); i++){
      |                 ~~^~~~~~~~~~
doll.cpp:87:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |  for(int i = 0; i < states.size(); i++){
      |                 ~~^~~~~~~~~~~~~~~
doll.cpp:95:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |  for(int i = 0; i < t.size(); i++){
      |                 ~~^~~~~~~~~~
doll.cpp:102:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |  for(int i = 0; i< C.size(); i++){
      |                 ~^~~~~~~~~~
doll.cpp:105:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |  for(int i = 0; i < X.size(); i++){
      |                 ~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 48 ms 5860 KB Output is correct
3 Correct 45 ms 6160 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 59 ms 8220 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 48 ms 5860 KB Output is correct
3 Correct 45 ms 6160 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 59 ms 8220 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 74 ms 11112 KB Output is correct
9 Correct 76 ms 11684 KB Output is correct
10 Correct 112 ms 14728 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 48 ms 5860 KB Output is correct
3 Correct 45 ms 6160 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 59 ms 8220 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 74 ms 11112 KB Output is correct
9 Correct 76 ms 11684 KB Output is correct
10 Correct 112 ms 14728 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 107 ms 14288 KB Output is correct
15 Correct 74 ms 10604 KB Output is correct
16 Correct 103 ms 13972 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 112 ms 14540 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 64 ms 9660 KB Output is correct
3 Correct 69 ms 9652 KB Output is correct
4 Correct 102 ms 12432 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 64 ms 9660 KB Output is correct
3 Correct 69 ms 9652 KB Output is correct
4 Correct 102 ms 12432 KB Output is correct
5 Correct 105 ms 13844 KB Output is correct
6 Correct 111 ms 13472 KB Output is correct
7 Correct 100 ms 13596 KB Output is correct
8 Correct 106 ms 13288 KB Output is correct
9 Correct 63 ms 9656 KB Output is correct
10 Correct 97 ms 13160 KB Output is correct
11 Correct 98 ms 12820 KB Output is correct
12 Correct 68 ms 9884 KB Output is correct
13 Correct 69 ms 10296 KB Output is correct
14 Correct 69 ms 10400 KB Output is correct
15 Correct 70 ms 10528 KB Output is correct
16 Correct 4 ms 588 KB Output is correct
17 Correct 91 ms 7880 KB Output is correct
18 Correct 80 ms 9916 KB Output is correct
19 Correct 68 ms 9912 KB Output is correct
20 Correct 97 ms 13076 KB Output is correct
21 Correct 97 ms 12820 KB Output is correct
22 Correct 103 ms 12928 KB Output is correct