제출 #135528

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
135528		Adhyyan1252	자동 인형 (IOI18_doll)	C++11	100 / 100	112 ms	14728 KiB

doll

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56