Submission #1063898

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063898		rlx0090	생일수 I (GA4_birthday1)	C++14	100 / 100	230 ms	30804 KiB

birthday1

#include <iostream>
#include <vector>
#include <fstream>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <cfloat>
#include <random>

using namespace std;

struct birthdayNumber {
	int len, three, five, eight;
	const bool operator<(const birthdayNumber& rhs) const {
		if(len != rhs.len) return len < rhs.len;
		if(three != rhs.three) return three < rhs.three;
		if(five != rhs.five) return five < rhs.five;
		return eight < rhs.eight;
	}
	const bool operator==(const birthdayNumber& rhs) const {
		return len == rhs.len && three == rhs.three && five == rhs.five && eight == rhs.eight;
	}
};
vector<birthdayNumber> cache(1e6 + 5, {987654321, 987654321, 987654321, 987654321});
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cache[3].len = 1;
	cache[3].three = 1;
	cache[5].len = 1;
	cache[5].five = 1;
	cache[6].len = 2;
	cache[6].three = 2;
	cache[8].len = 1;
	cache[8].eight = 1;

	for(int i = 9; i <= 1000000; ++i) {
		birthdayNumber a, b, c;
		a = cache[i - 3];
		b = cache[i - 5];
		c = cache[i - 8];
		birthdayNumber d = min({a, b, c});

		if(d == a) {
			cache[i] = a;
			cache[i].three++;
		} else if(d == b) {
			cache[i] = b;
			cache[i].five++;
		} else {
			cache[i] = c;
			cache[i].eight++;
		}
		cache[i].len++;
	}

	int t;
	cin >> t;
	// int rr = t;
	int e = 0;
	vector<string> a(t, "");
	while(t--) {
		int n;
		cin >> n;
		if(cache[n].len == 987654321){a[e++] = "-1"; cout << -1 << '\n';}
		else {
			if(cache[n].three >= 987654321) cache[n].three -= 987654321;
			if(cache[n].five >= 987654321) cache[n].five -= 987654321;
			if(cache[n].eight >= 987654321) cache[n].eight -= 987654321;
			// cout << cache[n].three << " " << cache[n].five << " " << cache[n].eight << endl;
			
			for(int i = 0; i < cache[n].three; ++i)
				a[e] += '3';
			for(int i = 0; i < cache[n].five; ++i)
				a[e] += '5';
			for(int i = 0; i < cache[n].eight; ++i)
				a[e] += '8';
			e++;
			// cout << '\n';
			
			for(int i = 0; i < cache[n].three; ++i)
				cout << 3;
			for(int i = 0; i < cache[n].five; ++i)
				cout << 5;
			for(int i = 0; i < cache[n].eight; ++i)
				cout << 8;
			cout << '\n';
		}
	}
	// for(int i = 0; i < rr; ++i) {
	// 	string s;
	// 	cin >> s;
	// 	if(s != a[i]) {
	// 		cout << "ans: " << s << " handed : " << a[i] << endl;
	// 	}
	// }
	return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 19 / 19
• Subtask 3: 26 / 26
• Subtask 4: 41 / 41