Submission #80028

ソースコード

?
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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <bits/extc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) begin(x),end(x)
#define updiv(a, b) (((a) + (b) - 1) / (b))
using ll = long long;
using ull = unsigned long long;
constexpr int INF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod1 = 1000000007;
constexpr int mod2 = 998244353;
template <class Func>
class FixPoint : Func {
public:
explicit constexpr FixPoint(Func&& f) noexcept : Func(forward<Func>(f)) {}
template <class... Args>
constexpr decltype(auto) operator()(Args&&... args) const {
return Func::operator()(*this, std::forward<Args>(args)...);
}
};
template <class Func>
static inline constexpr decltype(auto) makeFixPoint(Func&& f) noexcept {
return FixPoint<Func>{forward<Func>(f)};
}
template <class T, class It = decltype(std::begin(std::declval<T>()))>
inline constexpr auto Indexed(T&& iterable) {
struct Iterator {
size_t index;
It it;
constexpr bool operator!= (const Iterator& other) const { return it != other.it; }
constexpr void operator++() { ++index; ++it; }
constexpr void operator--() { --index; --it; }
constexpr auto operator*() const { return std::tie(index, *it); }
};
struct IterableWrapper {
T iterable;
constexpr auto begin() { return Iterator{ 0, std::begin(iterable) }; }
constexpr auto end() { return Iterator{ std::size(iterable), std::end(iterable) }; }
};
return IterableWrapper{ std::forward<T>(iterable) };
}
// {f(i) | i in [begin, left) ∪ (right, rbegin]}
template<class It, class F>
pair<It, reverse_iterator<It> > bsearch(It begin, It end, const F &f) {
auto rbegin = reverse_iterator(end), rend = reverse_iterator(begin);
if (begin == end) return make_pair(end, rend);
It left; reverse_iterator<It> right;
if (f(*begin)) {
auto l = begin, r = end;
while (r - l > 1) {
auto mid = l + (r - l) / 2;
if (f(*mid)) l = mid; else r = mid;
}
left = r;
} else left = begin;
if (f(*rbegin)) {
auto l = rbegin, r = rend;
while (r - l > 1) {
auto mid = l + (r - l) / 2;
if (f(*mid)) l = mid; else r = mid;
}
right = r;
} else right = rbegin;
return make_pair(left, right);
}
template<class T, class U> istream& operator>>(istream& is, pair<T, U>& p){ is >> p.first >> p.second; return (is); }
template<class T, class U> ostream& operator<<(ostream& os, pair<T, U>& p){ os << p.first << ' ' << p.second; return (os); }
template<class T> istream& operator>>(istream& is, vector<T>& v){ for (auto &&e : v) is >> e; return (is); }
template<class T> ostream& operator<<(ostream& os, vector<T>& v){ for (auto &&e : v) os << e << ' '; return (os); }
template<class T> inline const T& max(const vector<T> &v) { return *max_element(v.begin(), v.end()); }
template<class T> inline const T& min(const vector<T> &v) { return *min_element(v.begin(), v.end()); }
template<class T> inline T mex(vector<T> v) {
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for (T i = 0; i < (T) v.size(); ++i) if (v[i] != i) return i;
return v.size();
}
template<class T> inline T mex(initializer_list<T> l) { return mex(vector<T>(l)); }
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
template <class T> using max_heap = priority_queue<T>;
template <class T> using min_heap = priority_queue<T, vector<T>, greater<T> >;
template <class A, class B> using umap = unordered_map<A, B>;
template <class T> using uset = unordered_set<T>;
template <class T> using Max_Heap = __gnu_pbds::priority_queue<T, less<T>, __gnu_pbds::rc_binomial_heap_tag>;
template <class T> using Min_Heap = __gnu_pbds::priority_queue<T, greater<T>, __gnu_pbds::rc_binomial_heap_tag>;
template <class T> using Set = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
template <class K, class V> using Umap = __gnu_pbds::gp_hash_table<K, V>;
template <class T> using Rope = __gnu_cxx::rope<T>;
template <class T> void bye(T x){ cout << x << '\n'; exit(0); }
constexpr int dx[] = {1,0,-1,0,1,1,-1,-1,0};
constexpr int dy[] = {0,1,0,-1,1,-1,-1,1,0};
int main(){
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
cout.setf(ios_base::fixed);
cout.precision(12);
int n;
cin >> n;
vector<int> a(n);
cin >> a;
int n1 = n / 2;
int n2 = n / 2;
auto a1 = vector(a.begin(), a.begin() + n1);
auto a2 = vector(a.begin() + n1, a.end());
vector<umap<ll, bool> > mp(n / 2 + 1);
for (int bit = 0; bit < 1 << n1; ++bit) {
ll sum = 0;
int cnt1 = 0, cnt2 = 0;
for (int i = 0; i < n1; ++i) {
if (bit >> i & 1) sum += (ll) a1[i] * ++cnt1;
else sum -= (ll) a1[i] * ++cnt2;
}
mp[__builtin_popcount(bit)][sum] = true;
}
for (int bit = 0; bit < 1 << n2; ++bit) {
ll sum1 = 0, sum2 = 0, sum = 0;
int cnt1 = 0, cnt2 = 0;
for (int i = 0; i < n2; ++i) {
if (bit >> i & 1) {
sum += (ll) a2[i] * ++cnt1;
sum1 += a2[i];
} else {
sum -= (ll) a2[i] * ++cnt2;
sum2 += a2[i];
}
}
int pc = __builtin_popcount(bit);
if (mp[n1 - pc][-sum1 * (n1 - pc) + sum2 * pc - sum]) bye("Yes");
}
cout << "No\n";
return (0);
}

ステータス

項目 データ
問題 1815 - ボールの塗り分け
ユーザー名 ei1903
投稿日時 2024-07-19 12:01:17
言語 C++17
状態 Accepted
得点 1
ソースコード長 5871 Byte
最大実行時間 1078 ms
最大メモリ使用量 89864 KB

セット

セット 得点 Cases
1 ALL 1 / 1 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1.txt AC 99 ms 3032 KB
1
in2.txt AC 91 ms 1932 KB
1
in3.txt AC 20 ms 620 KB
1
in4.txt AC 416 ms 54904 KB
1
in5.txt AC 1061 ms 89628 KB
1
in6.txt AC 1078 ms 89864 KB
1
in7.txt AC 18 ms 616 KB
1
in8.txt AC 80 ms 11604 KB
1
in9.txt AC 18 ms 540 KB
1
in10.txt AC 25 ms 624 KB
1
in11.txt AC 21 ms 572 KB
1