제출 #524649

#제출 시각아이디문제언어결과실행 시간메모리
524649fatemetmhrNaan (JOI19_naan)C++17
29 / 100
1294 ms105344 KiB
// ~Be name khoda~ // #include<bits/stdc++.h> using namespace std; typedef long long ll; #define pb push_back #define mp make_pair #define all(x) x.begin(), x.end() #define fi first #define se second #define cl clear #define endll '\n' const int maxn = 1e6 + 10; const int maxn5 = 2e3 + 10; const int maxnt = 1.2e6 + 10; const int maxn3 = 1e3 + 10; const int mod = 1e9 + 7; const ll inf = 2e18; struct kasr{ ll s, m; kasr(ll a, ll b){ ll g = __gcd(a, b); s = a / g; m = b / g; } kasr(){ s = 0; m = 1; } inline ll ciel(){ ll f = s / m; if(s * f != m) f++; return f; } }; inline kasr operator -(ll a, kasr b){ a *= b.m; return kasr(a - b.s, b.m); } inline kasr operator -(kasr a, kasr b){ ll mm = a.m * b.m / __gcd(a.m, b.m); return kasr(a.s * (mm / a.m) - b.s * (mm / b.m), mm); } inline kasr operator +(kasr a, kasr b){ ll mm = a.m * b.m / __gcd(a.m, b.m); return kasr(a.s * (mm / a.m) + b.s * (mm / b.m), mm); } inline bool operator <=(kasr a, kasr b){ return a.s * b.m <= b.s * a.m; } inline bool operator >=(kasr a, kasr b){ return a.s * b.m >= b.s * a.m; } inline bool operator <(kasr a, kasr b){ return a.s * b.m < b.s * a.m; } inline bool operator >(kasr a, kasr b){ return a.s * b.m > b.s * a.m; } int n, l, per[maxn5]; ll a[maxn5][maxn5], ps[maxn5][maxn5]; kasr out[maxn5], have[maxn5][maxn5]; bool mark[maxn5]; inline ll get_val(int l, int r, int i){ if(l >= r) return 0; return ps[i][r] - ps[i][l]; } inline kasr cont(int i, kasr last, kasr ask){ //cout << "starting " << i << ' ' << last.s << ' ' << last.m << '\n'; kasr ret (0, 1); int id = last.ciel(); if(kasr(id, 1) > last){ kasr rem = id - last; kasr sup = kasr(ask.s, ask.m * a[i][id]); if(sup >= rem){ last = kasr(id, 1); ask = ask - kasr(rem.s * a[i][id], rem.m); } else{ return last + sup; } } int lo = id, hi = l + 1; while(hi - lo > 1){ int mid = (lo + hi) >> 1; if(kasr(get_val(id, mid, i), 1) <= ask) lo = mid; else hi = mid; } //cout << "ok " << lo << endl; last = kasr(lo, 1); ask = ask - kasr(get_val(id, lo, i), 1); if(ask.s == 0) return last; kasr sup = kasr(ask.s, ask.m * a[i][lo + 1]); //cout << ask.s << ' ' << ask.m << endl; return last + sup; } int main() { ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); cin >> n >> l; for(int i = 0; i < n; i++){ ll sum = 0; for(int j = 1; j <= l; j++){ cin >> a[i][j]; ps[i][j] = a[i][j] + ps[i][j - 1]; sum += a[i][j]; } kasr last(0, 1); for(int j = 0; j < n; j++){ //cout << i << ' ' << j << ' ' << last.s << ' ' << last.m << ' ' << sum << '\n'; last = have[i][j] = cont(i, last, kasr(sum, n)); } } //cout << have[1][0].s << ' ' << have[1][0].m << endl; for(int i = 0; i < n - 1; i++){ out[i] = kasr(l + 5, 1); per[i] = -1; for(int j = 0; j < n; j++) if(!mark[j] && have[j][i] < out[i]){ out[i] = have[j][i]; //cout << i << ' ' << j << ' ' << out[i].s << ' ' << out[i].m << endl; if(per[i] != -1) mark[per[i]] = false; per[i] = j; mark[j] = true; } cout << out[i].s << ' ' << out[i].m << '\n'; } for(int i = 0; i < n; i++) if(!mark[i]) per[n - 1] = i; for(int i = 0; i < n; i++){ cout << per[i] + 1 << ' '; } cout << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...