Submission #1063899

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063899		rlx0090	생일수 I (GA4_birthday1)	C++14	100 / 100	218 ms	22908 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);
	// ifstream cin;
	// cin.open("inputs.txt");
	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;
	while(t--) {
		int n;
		cin >> n;
		if(cache[n].len == 987654321) 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;
			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';
		}
	}
	return 0;
}

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