-
Notifications
You must be signed in to change notification settings - Fork 0
/
corbusier.cpp
115 lines (89 loc) · 2.21 KB
/
corbusier.cpp
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
//
// corbusier.cpp
// Algorithms Lab
//
// Created by Jonas Gessner
// Copyright © 2019 Jonas Gessner. All rights reserved.
//
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <string>
#include <unordered_set>
#include <vector>
using namespace std;
void testcase() {
int n, ii, k;
cin >> n >> ii >> k;
bool found = false;
vector<int> sumsFirst;
sumsFirst.push_back(0);
unordered_set<int> seen;
for (int i = 0; i < n / 2; i++) {
int disk;
cin >> disk;
if (found) {
continue;
}
int sumsCount = sumsFirst.size();
for (int j = 0; j < sumsCount; j++) {
int newSum = (sumsFirst.at(j) + disk) % k;
if (newSum == ii) {
found = true;
break;
}
if (seen.find(newSum) != seen.end()) {
continue;
}
sumsFirst.push_back(newSum);
seen.insert(newSum);
}
}
sort(sumsFirst.begin(), sumsFirst.end());
vector<int> sumsSecond;
sumsSecond.push_back(0);
unordered_set<int> seen2;
for (int i = n / 2; i < n; i++) {
int disk;
cin >> disk;
if (found) {
continue;
}
int sumsCount = sumsSecond.size();
for (int j = 0; j < sumsCount; j++) {
int newSum = (sumsSecond.at(j) + disk) % k;
if (newSum == ii) {
found = true;
break;
}
if (seen2.find(newSum) != seen2.end()) {
continue;
}
int needed = (ii - newSum);
if (needed < 0) {
needed += k;
}
needed %= k;
if (binary_search(sumsFirst.begin(), sumsFirst.end(), needed)) {
found = true;
break;
}
sumsSecond.push_back(newSum);
seen2.insert(newSum);
}
}
if (found) {
cout << "yes\n";
return;
}
cout << "no\n";
}
int main() {
std::ios_base::sync_with_stdio(false);
int t;
std::cin >> t;
for (int i = 0; i < t; ++i)
testcase();
}