Pagini recente » Monitorul de evaluare | Cod sursa (job #1419466) | Cod sursa (job #1839249)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("sate2.in");
ofstream fout("sate2.out");
struct group {
int size;
int s;
vector <int> v;
group() {
size = 0;
s = 0;
v = vector <int> ();
}
inline void move(int i, group &to) {
to.size++;
to.s += v[i];
to.v.push_back(v[i]);
size--;
s -= v[i];
swap(v[i], v[size]);
v.pop_back();
}
inline bool operator <(const group &other) const {
return s < other.s;
}
};
int n, m, k;
vector <group> grp;
mt19937 gen(time(nullptr));
bool solve() {
fin >> n >> m >> k;
if (n % k != 0)
return false;
grp.clear();
grp.resize(k);
for (int i = 0; i < n; i++) {
int x;
fin >> x;
grp.front().v.push_back(x);
grp.front().size++;
grp.front().s += x;
}
int iter = 150000;
while (iter > 0) {
auto imax = max_element(begin(grp), end(grp));
auto imin = min_element(begin(grp), end(grp));
if (imax->s == imin->s)
return true;
int i = labs(gen()) % imax->size;
imax->move(i, *imin);
iter--;
}
return true;
}
int main() {
int t;
fin >> t;
while (t--)
fout << (solve() ? "DA\n" : "NU\n");
return 0;
}