Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // ███▓▓▓▓▓▓▓▓▓╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬▓▓▓╬╬╬╬╬╬▓█
- // ███▓███████▓▓╬╬╬╬╬╬╬╬╬╬╬╬▓███▓▓▓▓█▓╬╬╬▓█
- // ███████▓█████▓▓╬╬╬╬╬╬╬╬▓███▓╬╬╬╬╬╬╬▓╬╬▓█
- // ████▓▓▓▓╬╬▓█████╬╬╬╬╬╬███▓╬╬╬╬╬╬╬╬╬╬╬╬╬█
- // ███▓▓▓▓╬╬╬╬╬╬▓██╬╬╬╬╬╬▓▓╬╬╬╬╬╬╬╬╬╬╬╬╬╬▓█
- // ████▓▓▓╬╬╬╬╬╬╬▓█▓╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬▓█
- // ███▓█▓███████▓▓███▓╬╬╬╬╬╬▓███████▓╬╬╬╬▓█
- // ████████████████▓█▓╬╬╬╬╬▓▓▓▓▓▓▓▓╬╬╬╬╬╬╬█
- // ███▓▓▓▓▓▓▓╬╬▓▓▓▓▓█▓╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬▓█
- // ████▓▓▓╬╬╬╬▓▓▓▓▓▓█▓╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬▓█
- // ███▓█▓▓▓▓▓▓▓▓▓▓▓▓▓▓╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬▓█
- // █████▓▓▓▓▓▓▓▓█▓▓▓█▓╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬▓█
- // █████▓▓▓▓▓▓▓██▓▓▓█▓╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██
- // █████▓▓▓▓▓████▓▓▓█▓╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██
- // ████▓█▓▓▓▓██▓▓▓▓██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██
- // ████▓▓███▓▓▓▓▓▓▓██▓╬╬╬╬╬╬╬╬╬╬╬╬█▓╬▓╬╬▓██
- // █████▓███▓▓▓▓▓▓▓▓████▓▓╬╬╬╬╬╬╬█▓╬╬╬╬╬▓██
- // █████▓▓█▓███▓▓▓████╬▓█▓▓╬╬╬▓▓█▓╬╬╬╬╬╬███
- // ██████▓██▓███████▓╬╬╬▓▓╬▓▓██▓╬╬╬╬╬╬╬▓███
- // ███████▓██▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓╬╬╬╬╬╬╬╬╬╬╬████
- // ███████▓▓██▓▓▓▓▓╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬▓████
- // ████████▓▓▓█████▓▓╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬▓█████
- // █████████▓▓▓█▓▓▓▓▓███▓╬╬╬╬╬╬╬╬╬╬╬▓██████
- // ██████████▓▓▓█▓▓▓╬▓██╬╬╬╬╬╬╬╬╬╬╬▓███████
- // ███████████▓▓█▓▓▓▓███▓╬╬╬╬╬╬╬╬╬▓████████
- // ██████████████▓▓▓███▓▓╬╬╬╬╬╬╬╬██████████
- // ███████████████▓▓▓██▓▓╬╬╬╬╬╬▓███████████
- #pragma GCC optimize("Ofast")
- #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
- #pragma GCC optimize("unroll-loops")
- #include <bits/stdc++.h>
- #define pb push_back
- #define x first
- #define y second
- #define mp make_pair
- #define len(a) int(a.size())
- #define files(FILENAME) read(FILENAME); write(FILENAME)
- #define read(FILENAME) freopen((string(FILENAME) + ".in").c_str(), "r", stdin)
- #define write(FILENAME) freopen((string(FILENAME) + ".out").c_str(), "w", stdout)
- using namespace std;
- template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
- template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; }
- template<typename T, typename U> inline ostream &operator<< (ostream &_out, const pair<T, U> &_p) { _out << _p.first << ' ' << _p.second; return _out; }
- template<typename T, typename U> inline istream &operator>> (istream &_in, pair<T, U> &_p) { _in >> _p.first >> _p.second; return _in; }
- template<typename T> inline ostream &operator<< (ostream &_out, const vector<T> &_v) { if (_v.empty()) { return _out; } _out << _v.front(); for (auto _it = ++_v.begin(); _it != _v.end(); ++_it) { _out << ' ' << *_it; } return _out; }
- template<typename T> inline istream &operator>> (istream &_in, vector<T> &_v) { for (auto &_i : _v) { _in >> _i; } return _in; }
- template<typename T> inline ostream &operator<< (ostream &_out, const set<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
- template<typename T> inline ostream &operator<< (ostream &_out, const multiset<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
- template<typename T> inline ostream &operator<< (ostream &_out, const unordered_set<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
- template<typename T> inline ostream &operator<< (ostream &_out, const unordered_multiset<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
- template<typename T, typename U> inline ostream &operator<< (ostream &_out, const map<T, U> &_m) { if (_m.empty()) { return _out; } _out << '(' << _m.begin()->first << ": " << _m.begin()->second << ')'; for (auto _it = ++_m.begin(); _it != _m.end(); ++_it) { _out << ", (" << _it->first << ": " << _it->second << ')'; } return _out; }
- template<typename T, typename U> inline ostream &operator<< (ostream &_out, const unordered_map<T, U> &_m) { if (_m.empty()) { return _out; } _out << '(' << _m.begin()->first << ": " << _m.begin()->second << ')'; for (auto _it = ++_m.begin(); _it != _m.end(); ++_it) { _out << ", (" << _it->first << ": " << _it->second << ')'; } return _out; }
- typedef long long base;
- typedef pair<int, int> point;
- typedef complex<double> comp;
- const int N = 2e3 + 5;
- int n, m;
- long long s[N];
- long long v[N][N];
- pair<long long, long long> take[N][N];
- long long gcd(long long a, long long b) {
- return a == 0 ? b : gcd(b % a, a);
- }
- bool compare(pair<long long, long long> &a, pair<long long, long long> &b) {
- return (__int128) a.x * b.y < (__int128) b.x * a.y;
- }
- int main() {
- ios::sync_with_stdio(0);
- srand(time(0));
- //read("input");
- cin >> n >> m;
- for (int i = 1; i <= n; ++i) {
- for (int j = 0; j < m; ++j) {
- cin >> v[i][j];
- v[i][j] *= n;
- s[i] += v[i][j];
- }
- s[i] /= n;
- long long cur = 0;
- take[i][0] = {m, 1};
- int t = 1;
- for (int j = m; j--;) {
- long long vx = v[i][j];
- while (vx > 0) {
- auto k = min(vx, s[i] - cur);
- cur += k;
- vx -= k;
- if (cur == s[i]) {
- cur -= s[i];
- take[i][t++] = {j * v[i][j] + vx, v[i][j]};
- }
- }
- }
- }
- vector<int> alive;
- vector<int> who;
- vector<int> order;
- for (int i = 1; i <= n; ++i) {
- who.pb(i);
- }
- while (who.size() > 1) {
- int it = 0;
- for (int i = 1; i < who.size(); ++i) {
- if (compare(take[who[i]][(int)who.size() - 1], take[who[it]][(int)who.size() - 1])) {
- it = i;
- }
- }
- auto v = gcd(take[who[it]][(int)who.size() - 1].x, take[who[it]][(int)who.size() - 1].y);
- take[who[it]][(int)who.size() - 1].x /= v;
- take[who[it]][(int)who.size() - 1].y /= v;
- cout << take[who[it]][(int)who.size() - 1] << '\n';
- order.pb(who[it]);
- who.erase(who.begin() + it);
- }
- order.pb(who[0]);
- cout << order << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement