Submission #699173

#TimeUsernameProblemLanguageResultExecution timeMemory
699173dooweyNaan (JOI19_naan)C++14
5 / 100
1 ms340 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; #define fi first #define se second #define mp make_pair #define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); const int N = 2010; struct frac{ ll A; ll B; void normalize(){ ll g = __gcd(A, B); A /= g; B /= g; } frac operator+ (frac y){ frac T = {A * y.B + B * y.A, B * y.B}; T.normalize(); return T; } frac operator- (frac y){ frac T = {A * y.B - B * y.A, B * y.B}; T.normalize(); return T; } bool operator< (frac y){ return (A * y.B - B * y.A < 0); } }; ll V[N][N]; ll S[N][N]; int m; frac calc(int id, frac P){ int las = P.A / P.B; frac Y = {S[id][las], 1}; frac add = (P - (frac){las, 1}); add.A *= V[id][las + 1]; Y = Y + add; return Y; } frac need[N]; bool use[N]; int pi[N]; int main(){ fastIO; //freopen("in.txt", "r", stdin); int n; cin >> n >> m; for(int i = 1; i <= n; i ++ ){ need[i] = {0, n}; for(int j = 1; j <= m ; j ++ ){ cin >> V[i][j]; need[i].A += V[i][j]; S[i][j] = V[i][j] + S[i][j - 1]; } pi[i] = -1; } frac las = {0, 1}; frac tis; frac nx; frac cur; frac low; int idx; frac S; ll X; for(int it = 1; it < n; it ++ ){ low = {m, 1}; idx = -1; for(int i = 1; i <= n; i ++ ){ if(!use[i]){ tis = calc(i, las); for(int j = 1; j <= m; j ++ ){ nx = calc(i, {j, 1}); if(need[i] < nx - tis){ S = nx - tis; S = S - need[i]; S.A *= (ll)n; X = S.A / S.B; tis = (frac){j, 1} - (frac){X, n * 1ll * V[i][j]}; if(tis < low){ low = tis; idx = i; } break; } } } } pi[it] = idx; use[idx]=true; las = low; cout << low.A << " " << low.B << "\n"; } for(int i = 1; i <= n; i ++ ){ if(!use[i]){ pi[n]=i; } } for(int i = 1; i <= n; i ++ ){ cout << pi[i] << " "; } cout << "\n"; return 0; }

Compilation message (stderr)

naan.cpp: In function 'int main()':
naan.cpp:72:10: warning: unused variable 'cur' [-Wunused-variable]
   72 |     frac cur;
      |          ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...