제출 #762223

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
762223		minhcool	자동 인형 (IOI18_doll)	C++17	75.55 / 100	116 ms	27128 KiB

doll

//#define local
#ifndef local
#include "doll.h"
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 5e5 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

mt19937 rng(1);

int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}

int cnt = 0;

int c[N], x[N], y[N];

vector<int> nxts[N];

int rt;

void create(int where, vector<int> v){
//	cout << "OKOKOK " << where << " " << v.size() << "\n";
	if(v.size() == 2){
	//	cout << v[0] << " " << v[1] << "\n";
		x[where] = v[0], y[where] = v[1];
		return;
	}
	vector<int> v1, v2;
	//cnt++;
	//x[where] = -cnt;
	for(int i = 0; i < v.size(); i += 2) v1.pb(v[i]);
	bool ck = 0;
	for(auto it : v1) ck |= (it >= 0);
	if(ck){	
		cnt++;
		x[where] = -cnt;
		create(cnt, v1);
	}
	else x[where] = rt;
	for(int i = 1; i < v.size(); i += 2) v2.pb(v[i]);
	ck = 0;
	for(auto it : v2) ck |= (it >= 0);
	if(ck){	
		cnt++;
		y[where] = -cnt;
		create(cnt, v2);
	}
	else y[where] = rt;
}

void create_circuit(int M, vector<int> A){
 	A.pb(0);
  	for(int i = 0; (i + 1) < A.size(); i++) nxts[A[i]].pb(A[i + 1]);
  	c[0] = A[0];
  	int cntt = 0;
  	for(int i = 1; i <= M; i++){
  		if(nxts[i].size() == 0) nxts[i].pb(1);
  		if(nxts[i].size() <= 1){
  			c[i] = nxts[i][0];
  			continue;
		}
		int pw = 1;
		while(pw < nxts[i].size()) pw *= 2;
		cntt += (pw - 1);
		//cnt++;
		//c[i] = -cnt;
		//create(cnt, nxts[i]);
	}
//	cout << "HEHE " << cntt << "\n";
//	cout << cntt << "\n";
	int temp = cntt;
	for(int i = 1; i <= M; i++){
		if(nxts[i].size() <= 1) continue;
		int pw = 1;
		while(pw < nxts[i].size()) pw *= 2;
		cnt++;
		c[i] = -cnt;
		rt = -cnt;
		if(pw > nxts[i].size()){
		vector<int> nw;
		reverse(nxts[i].begin(), nxts[i].end());
		int cnt = pw - nxts[i].size();
		for(int j = 0; j < pw; j++){
			if(!(j & 1)){
				if(cnt){
					nw.pb(rt);
					cnt--;
				}
				else{
				//	assert(nxts[i].size());
					nw.pb(nxts[i].back());
					nxts[i].pop_back();
				}
			}
			else{
			//	assert(nxts[i].size());
				nw.pb(nxts[i].back());
				nxts[i].pop_back();
			}
		}
		nxts[i] = nw;
		//reverse(nxts[i].begin(), nxts[i].end());
		//cntt++;
		//reverse(nxts[i].begin(), nxts[i].end());
	}
		//cnt++;
		create(cnt, nxts[i]);
	}
	/*
	for(int i = 1; i <= cnt; i++){
		if(x[i] < -cnt) x[i] = (-(cnt + (-x[i]) - temp)); 
		if(y[i] < -cnt) x[i] = (-(cnt + (-x[i]) - temp)); 
	}
	for(int i = temp + 1; i <= cntt; i++){
		x[i - (temp - cnt)] = x[i];
		y[i - (temp - cnt)] = y[i];
	}*/
//	cout << cnt << "\n";
	vector<int> C(M + 1), X(cnt), Y(cnt);
	for(int i = 0; i <= M; i++) C[i] = c[i];
	for(int i = 1; i <= cnt; i++){
		X[i - 1] = x[i], Y[i - 1] = y[i];
	}
	answer(C, X, Y);
}

#ifdef local
void process(){

}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while(t--) process();
}
#endif

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

doll.cpp:22:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   22 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~
doll.cpp: In function 'void create(int, std::vector<int>)':
doll.cpp:49:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(int i = 0; i < v.size(); i += 2) v1.pb(v[i]);
      |                 ~~^~~~~~~~~~
doll.cpp:58:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(int i = 1; i < v.size(); i += 2) v2.pb(v[i]);
      |                 ~~^~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:71:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |    for(int i = 0; (i + 1) < A.size(); i++) nxts[A[i]].pb(A[i + 1]);
      |                   ~~~~~~~~^~~~~~~~~~
doll.cpp:81:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |   while(pw < nxts[i].size()) pw *= 2;
      |         ~~~^~~~~~~~~~~~~~~~
doll.cpp:93:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |   while(pw < nxts[i].size()) pw *= 2;
      |         ~~~^~~~~~~~~~~~~~~~
doll.cpp:97:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |   if(pw > nxts[i].size()){
      |      ~~~^~~~~~~~~~~~~~~~
doll.cpp:89:6: warning: unused variable 'temp' [-Wunused-variable]
   89 |  int temp = cntt;
      |      ^~~~

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 12.421421913600001 / 18
• Subtask 6: 37.1243889072 / 56