Submission #944118

# Submission time Handle Problem Language Result Execution time Memory
944118 2024-03-12T08:40:21 Z shoryu386 Mechanical Doll (IOI18_doll) C++17
6 / 100
61 ms 13316 KB
#include <bits/stdc++.h>
using namespace std;
int ptr = -1;
vector<int> xLead, yLead;
#include "doll.h"

int construct(vector<int> item){
	if (item.size() == 1){
		return item[0];
	}
	
	vector<int> itemLeft, itemRight;
	for (int x = 0; x < item.size(); x+=2){
		itemLeft.push_back(item[x]);
	}
	for (int x = 1; x < item.size(); x+=2){
		itemRight.push_back(item[x]);
	}
	
	int curNode = ptr;
	
	//cerr << "Construct " << curNode << '\n';
	//for (auto y : item) cerr << y << ' ';
	//cerr << '\n';
	
	ptr--;
	xLead[-curNode - 1] = ( construct(itemLeft) );
	yLead[-curNode - 1] = ( construct(itemRight) );
	
	return curNode;
}


void create_circuit(int m, std::vector<int> A) {
	int n = A.size();
	xLead.clear(); yLead.clear();
	xLead.resize(2*n + 100); yLead.resize(2*n + 100);
	ptr = -1;
	
	vector<int> leads[m+1];
	
	leads[0].push_back(A[0]);
	for (int x = 0; x < n-1; x++){
		leads[A[x]].push_back(A[x+1]);
	}
	leads[A[n-1]].push_back(0);
	
	vector<int> connection(m+1);
	for (int x = 0; x <= m; x++){
		if (leads[x].size() == 0){
			connection[x] = x;
		}
		else if (leads[x].size() == 1){
			connection[x] = leads[x][0];
		}
		else{
			//construct binary tree
			connection[x] = construct(leads[x]);
		}
		
		//cerr << "leads " << x << '\n';
		//for (auto y : leads[x]){
		//	cerr << y << ' ';
		//}
		//cerr << '\n';
	}
	
	xLead.resize(-ptr - 1); yLead.resize(-ptr - 1);
	answer(connection, xLead, yLead);
}

Compilation message

doll.cpp: In function 'int construct(std::vector<int>)':
doll.cpp:14:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for (int x = 0; x < item.size(); x+=2){
      |                  ~~^~~~~~~~~~~~~
doll.cpp:17:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for (int x = 1; x < item.size(); x+=2){
      |                  ~~^~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 19 ms 7768 KB Output is correct
3 Correct 20 ms 6236 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 9 ms 3932 KB Output is correct
6 Correct 24 ms 9308 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 19 ms 7768 KB Output is correct
3 Correct 20 ms 6236 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 9 ms 3932 KB Output is correct
6 Correct 24 ms 9308 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 37 ms 8796 KB Output is correct
9 Correct 45 ms 10304 KB Output is correct
10 Correct 58 ms 13316 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 19 ms 7768 KB Output is correct
3 Correct 20 ms 6236 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 9 ms 3932 KB Output is correct
6 Correct 24 ms 9308 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 37 ms 8796 KB Output is correct
9 Correct 45 ms 10304 KB Output is correct
10 Correct 58 ms 13316 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Incorrect 61 ms 11624 KB state 'Y'
15 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB state 'Y'
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB state 'Y'
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB state 'Y'
2 Halted 0 ms 0 KB -