Submission #162930

#TimeUsernameProblemLanguageResultExecution timeMemory
162930combi1k1Naan (JOI19_naan)C++14
100 / 100
1810 ms134792 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define FOR(i,a,b) for(int i = a ; i < b ; ++i) const int N = 2e3 + 1; const int inf = 1e9 + 7; struct Frac { ll int_part; ll upper; ll lower; Frac(ll a = 0,ll b = 0,ll c = 0) { int_part = a; upper = b; lower = c; if (b > c) { int_part += b / c; upper %= c; } ll g = __gcd(abs(b),abs(c)); upper /= g; lower /= g; if (c < 0) upper *= (-1), lower *= (-1); }; }; bool operator < (const Frac &lhs,const Frac &rhs) { if (lhs.int_part != rhs.int_part) return lhs.int_part < rhs.int_part; return lhs.upper * rhs.lower < lhs.lower * rhs.upper; } ostream & operator << (ostream &out,Frac &C) { ll a = C.int_part * C.lower + C.upper; ll b = C.lower; out << a << " "; out << b << "\n"; return out; } int v[N][N]; ll s[N]; vector<Frac> cut[N]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; int L; cin >> L; FOR(i,0,n) FOR(j,0,L) { cin >> v[i][j]; s[i] += v[i][j]; } FOR(i,0,n) { ll sum = 0; int ptr = 0; FOR(j,1,n) { for(; (sum + v[i][ptr]) * n <= s[i] * j ; ++ptr) sum += v[i][ptr]; ll lower = v[i][ptr] * n; ll upper = s[i] * j - sum * n; cut[i].pb({ptr,upper,lower}); } cut[i].pb({L,0,1}); } vector<int> perm; vector<int> have; FOR(i,0,n) have.push_back(i); FOR(i,0,n) { sort(have.begin(),have.end(),[&](int x,int y) { return cut[y][i] < cut[x][i]; }); perm.push_back(have.back()); have.pop_back(); if (i < n - 1) cout << cut[perm.back()][i]; } for(int x : perm) cout << x + 1 << " "; } /* 2 5 2 7 1 8 2 3 1 4 1 5 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...