oj.uz

답안 #783208

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
783208 2023-07-14T17:46:55 Z APROHACK 자동 인형 (IOI18_doll) C++14
6 / 100
 51 ms 16980 KB 
#include <bits/stdc++.h>
#include "doll.h"
#define ll long long
#define pb push_back
#define ff first
#define ss second
using namespace std;

int n;
int currentSwitch = 1;
vector<int>goes[100002];
vector<int>c, x, y;
vector<int>potencias2;
bool isPot(int k){
	while(k > 1){
		if(k % 2 == 1)return false;
		k/=2;
	}
	return true;
}
int principio, puntero;

int generar(int vec, int desde, int cada, int cuantosHay, bool up){
	//cout << "generando " << vec << " desde " << desde << " " << cada << "hay " << cuantosHay << endl;
	int tam = goes[vec].size()-desde;
	int cuantosReal = (tam + cada-1)/cada;
	if(cuantosReal == 1 and cuantosHay == 1){
		return goes[vec][desde];
	}
	if(cuantosReal <= 0 and cuantosHay == 1){
		if(!up){
			return principio;
		}else{
			return INT_MAX;
		}
	}
	
	x.pb(0);
	y.pb(0);
	int estoy = currentSwitch ++ ; // 1
	x[estoy-1] = generar(vec, desde, cada * 2, cuantosHay/2, false);
	y[estoy-1] = generar(vec, desde + cada, cada*2, cuantosHay/2, up);
	if(y[estoy-1] == INT_MAX)puntero = estoy-1;
	return (-estoy);
}

void create_circuit(int M, std::vector<int> A) {
	n = A.size();
	for(int i = 1 ; i < n ; i ++){
		goes[A[i-1]].pb(A[i]);
	}
	int temp = 1;
	while(temp < 2000000){
		potencias2.pb(temp);
		temp*= 2;
	}
	int ultimo = A.back();
	//goes[A.back()].pb(0);
	bool vis[M+1];
	memset(vis,false, sizeof vis);
	c.pb(A[0]);
	vector<pair<int, int> > toRepair; // switch inicio, indice Y final
	for(int i = 1 ; i <= M ; i ++)c.pb(0);
	for(int i = 0 ; i < n ; i ++){
		if(A[i] == ultimo)continue;
		if(!vis[A[i]]){
			vis[A[i]] = true;
			principio = -currentSwitch;
			int nextPot = 1;
			while(nextPot < goes[A[i]].size())nextPot*=2;
			c[A[i]] = generar(A[i], 0, 1, nextPot, true);
			if(!isPot(goes[A[i]].size())){
				toRepair.pb({c[A[i]], puntero});
				//cout << "ins " << c[A[i]] << " " <<  puntero << endl;
			}
		}
	}
	if(goes[ultimo].size() == 0){
		if(toRepair.size() == 0){
			c[ultimo] = 0;
			answer(c, x, y);
			return ;
		}else{
			c[ultimo] = toRepair.back().ff;
		}
	}else{
		principio = -currentSwitch;
		int nextPot = 1;
		while(goes[ultimo].size() and nextPot < goes[ultimo].size())nextPot*=2;
		if(nextPot == goes[ultimo].size()){
			c[ultimo] = generar(ultimo, 0, 1, nextPot*2, true);
			toRepair.pb({c[ultimo], puntero});
		}else {
			c[ultimo] = generar(ultimo, 0, 1, nextPot, true);
			toRepair.pb({c[ultimo], puntero});
		}
	}
	
	for(int i = toRepair.size() -1 ; i > 0 ; i --){
		//cout << "end " << toRepair[i].ss << " to " << toRepair[i-1].ff << endl;
		y[toRepair[i].ss] = toRepair[i-1].ff;
	}
	y[toRepair[0].ss] = 0;
	answer(c, x, y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:70:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |    while(nextPot < goes[A[i]].size())nextPot*=2;
      |          ~~~~~~~~^~~~~~~~~~~~~~~~~~~
doll.cpp:89:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |   while(goes[ultimo].size() and nextPot < goes[ultimo].size())nextPot*=2;
      |                                 ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
doll.cpp:90:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |   if(nextPot == goes[ultimo].size()){
      |      ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 21 ms 7000 KB Output is correct
3 Correct 16 ms 6544 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 8 ms 4044 KB Output is correct
6 Correct 27 ms 8636 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 21 ms 7000 KB Output is correct
3 Correct 16 ms 6544 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 8 ms 4044 KB Output is correct
6 Correct 27 ms 8636 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 44 ms 9772 KB Output is correct
9 Correct 35 ms 9784 KB Output is correct
10 Correct 51 ms 12788 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 1 ms 2644 KB Output is correct
13 Correct 1 ms 2644 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 21 ms 7000 KB Output is correct
3 Correct 16 ms 6544 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 8 ms 4044 KB Output is correct
6 Correct 27 ms 8636 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 44 ms 9772 KB Output is correct
9 Correct 35 ms 9784 KB Output is correct
10 Correct 51 ms 12788 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 1 ms 2644 KB Output is correct
13 Correct 1 ms 2644 KB Output is correct
14 Runtime error 33 ms 16980 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 5144 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 5080 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 5080 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -