blob: 179598bb3c565185d7a8830744b7b132ab8c0599 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
|
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <bitset>
#include <functional>
#include <cstdlib>
#include <climits>
#include <ctime>
#include <cassert>
static double time_func(std::function<void()> func) {
const double minmeasure = 2.0;
const double factor = 1.5;
for (int reps = 1;
reps < INT_MAX / factor;
reps = std::max<int>(reps + 1, reps * factor)) {
const clock_t t_start = clock();
for (int k = 0; k < reps; k++) func();
const clock_t t_end = clock();
const double time_taken = (double)(t_end - t_start) / CLOCKS_PER_SEC;
std::cerr << reps << "x -> " << time_taken << "s" << std::endl;
if (time_taken >= minmeasure) return time_taken / reps;
}
assert(false);
}
static std::string read_input() {
std::ios::sync_with_stdio(false);
std::ifstream file{"1.in"};
file.seekg(0, std::ios::end);
size_t filesize = file.tellg();
file.seekg(0);
std::string input(filesize, '\0');
size_t cursor = 0;
while (cursor < filesize) {
file.read(&input[cursor], filesize - cursor);
cursor += file.gcount();
}
return input;
}
static std::pair<int, int> solve(const std::string &input) {
std::vector<int> numbers;
numbers.reserve(input.size() / 2);
std::bitset<2021> have;
char *endp = nullptr;
const char *cursor = input.data();
while (true) {
int val = strtol(cursor, &endp, 10);
if (endp == cursor) break;
numbers.push_back(val);
have[val] = true;
cursor = endp;
}
int ans1 = -1;
for (int n : numbers) {
if (2020 - n >= 0 && have[2020 - n]) {
ans1 = n * (2020 - n);
break;
}
}
for (int n : numbers) {
for (int m : numbers) {
const int k = 2020 - (n + m);
if (k >= 0 && have[k]) {
return std::make_pair(ans1, n * m * k);
}
}
}
assert(false);
}
int main() {
const std::string input = read_input();
auto out = solve(input);
std::cout << out.first << '\n' << out.second << std::endl;
std::cout << time_func([&input](){ solve(input); }) << std::endl;
}
|
