| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 524428 | 2022-02-09T08:12:09 Z | ParsaAlizadeh | Naan (JOI19_naan) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define all(x) begin(x), end(x)
#define kill(x) return cout << x << '\n', 0
#define fst first
#define snd second
void assume(int expr) {
if (!expr) __builtin_unreachable();
}
constexpr int N = 2e3 + 10;
struct Ratio {
ll x, y;
Ratio() : x(0), y(1) {}
Ratio(ll x) : x(x), y(1) {}
Ratio(ll x, ll y) : x(x), y(y) {
norm();
}
void norm() {
ll g = __gcd(x, y);
x /= g;
y /= g;
if (y < 0) {
x *= -1;
y *= -1;
}
}
Ratio operator+(Ratio const& r) const {
return Ratio{x * r.y + r.x * y, y * r.y};
}
Ratio operator*(Ratio const& r) const {
return Ratio{x * r.x, y * r.y};
}
bool operator<(Ratio const& r) const {
return x * r.y < y * r.x;
}
};
struct Event {
Ratio start;
int person, ind;
bool operator<(Event const& oth) const {
if (ind != oth.ind)
return ind < oth.ind;
return start < oth.start;
}
};
int n, L, P[N];
ll V[N][N];
vector<Event> E;
vector<Ratio> ans;
bitset<N> mark;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> L;
for (int i = 0; i < n; i++) {
ll S = 0;
vector<ll> vec;
vec.reserve(L+1);
vec.push_back(0);
for (int j = 0; j < L; j++) {
cin >> V[i][j];
S += V[i][j];
vec.push_back(S * n);
}
for (int j = 1; j <= n; j++) {
ll x = S * j;
int k = upper_bound(all(vec), x) - begin(vec);
k--;
Ratio start = k;
x -= vec[k];
if (k < L)
start = start + Ratio{x, n * V[i][k]};
E.push_back(Event(start, i, j));
}
}
sort(all(E));
fill(all(P), -1);
for (auto const& e : E) {
if (mark[e.person]) continue;
if (P[e.ind] != -1) continue;
P[e.ind] = e.person;
mark[e.person] = true;
ans.push_back(e.start);
}
ans.pop_back();
for (auto const& r : ans) {
cout << r.x << ' ' << r.y << '\n';
}
for (int i = 1; i <= n; i++) {
cout << P[i]+1 << ' ';
}
cout << '\n';
return 0;
}