/*input
7 1
1
2
3
4
5
6
7
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// credit: https://codeforces.com/blog/entry/66022?#comment-500539
struct Frac
{
uint64_t nume, demo;
Frac(uint64_t _nume = 0, uint64_t _demo = 1): nume(_nume), demo(_demo) {}
bool operator<(const Frac fr) const
{
return nume * fr.demo < fr.nume * demo;
}
bool operator<=(const Frac fr) const
{
return nume * fr.demo <= fr.nume * demo;
}
bool operator==(const Frac fr) const
{
return nume * fr.demo == fr.nume * demo;
}
Frac operator+(const uint64_t x) const
{
return {nume + demo * x, demo};
}
Frac operator-(const uint64_t x) const
{
return {nume - demo * x, demo};
}
Frac operator/ (const uint64_t x) const
{
return {nume, demo * x};
}
friend ostream& operator<< (ostream &os, const Frac fr)
{
return os << fr.nume << ' ' << fr.demo;
}
};
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
uint32_t N, L;
cin >> N >> L;
vector<vector<uint32_t>> V(N, vector<uint32_t>(L));
for (auto &vec : V) for (auto &i : vec) cin >> i;
vector<vector<Frac>> joints(N, vector<Frac>(N, {0, 1}));
for (uint32_t person = 0; person < N; ++person) {
uint32_t total = accumulate(V[person].begin(), V[person].end(), (uint32_t) 0);
uint32_t flavor = 0, happiness = 0;
for (uint32_t split = 1; split < N; ++split) {
Frac target(total * split, N);
while (Frac(happiness + V[person][flavor], 1) <= target) {
happiness += V[person][flavor];
++flavor;
}
joints[person][split] = ((target - happiness) / V[person][flavor]) + flavor;
}
}
vector<uint32_t> P(N);
vector<bool> used(N, false);
for (uint32_t joint = 1; joint < N; ++joint) {
uint32_t candidate = N;
for (uint32_t person = 0; person < N; ++person) {
if ((not used[person]) and (candidate == N or joints[person][joint] < joints[candidate][joint])) {
candidate = person;
}
}
P[joint - 1] = candidate;
used[candidate] = true;
cout << joints[candidate][joint] << '\n';
}
for (uint32_t person = 0; person < N; ++person) {
if (not used[person]) {
P[N - 1] = person;
break;
}
}
for (auto person : P) {
cout << person + 1 << ' ';
}
return 0;
}
Compilation message
naan.cpp: In function 'int main()':
naan.cpp:71:20: error: 'accumulate' was not declared in this scope
uint32_t total = accumulate(V[person].begin(), V[person].end(), (uint32_t) 0);
^~~~~~~~~~
