Submission #1063899

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1063899	2024-08-18T05:49:14 Z	rlx0090	생일수 I (GA4_birthday1)	C++14	100 / 100	218 ms	22908 KB

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.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	15960 KB	Output is correct

Subtask #2

19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	15964 KB	Output is correct

Subtask #3

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	15964 KB	Output is correct
2	Correct	13 ms	15960 KB	Output is correct
3	Correct	15 ms	15964 KB	Output is correct
4	Correct	13 ms	15960 KB	Output is correct
5	Correct	14 ms	15964 KB	Output is correct
6	Correct	13 ms	15876 KB	Output is correct
7	Correct	13 ms	15964 KB	Output is correct
8	Correct	13 ms	15964 KB	Output is correct
9	Correct	14 ms	16120 KB	Output is correct
10	Correct	13 ms	15964 KB	Output is correct

Subtask #4

41.0 / 41.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	200 ms	22764 KB	Output is correct
2	Correct	175 ms	22016 KB	Output is correct
3	Correct	196 ms	22908 KB	Output is correct
4	Correct	191 ms	22572 KB	Output is correct
5	Correct	181 ms	22240 KB	Output is correct
6	Correct	198 ms	22896 KB	Output is correct
7	Correct	171 ms	21920 KB	Output is correct
8	Correct	204 ms	22352 KB	Output is correct
9	Correct	195 ms	22880 KB	Output is correct
10	Correct	174 ms	22096 KB	Output is correct
11	Correct	189 ms	22356 KB	Output is correct
12	Correct	170 ms	21840 KB	Output is correct
13	Correct	191 ms	22616 KB	Output is correct
14	Correct	186 ms	22352 KB	Output is correct
15	Correct	170 ms	21996 KB	Output is correct
16	Correct	187 ms	22376 KB	Output is correct
17	Correct	187 ms	22616 KB	Output is correct
18	Correct	174 ms	21844 KB	Output is correct
19	Correct	175 ms	22096 KB	Output is correct
20	Correct	172 ms	21600 KB	Output is correct
21	Correct	218 ms	22608 KB	Output is correct
22	Correct	191 ms	22432 KB	Output is correct
23	Correct	189 ms	22612 KB	Output is correct
24	Correct	197 ms	22608 KB	Output is correct
25	Correct	204 ms	22608 KB	Output is correct