Submission #131827

#TimeUsernameProblemLanguageResultExecution timeMemory
131827SirCenessNaan (JOI19_naan)C++14
100 / 100
919 ms125896 KiB
#include <bits/stdc++.h> using namespace std; #define mod 998244353 #define mp make_pair #define pb push_back #define bas(x) #x << ": " << x << " " #define prarr(x, n) cout << #x << ": "; for (int qsd = 0; qsd < n; qsd++) cout << x[qsd] << " "; cout << endl; #define prarrv(x) cout << #x << ": "; for (int qsd = 0; qsd < (int)x.size(); qsd++) cout << x[qsd] << " "; cout << endl; #define inside sl<=l%&&r<=sr #define outside sr<l||r<sl typedef long long ll; int n, m; ll mat[2002][2002]; ll presum[2002][2002]; pair<ll, ll> bol[2002][2002]; vector<pair<ll, ll> > ans; vector<int> p; pair<ll, ll> sum(pair<ll, ll> a, pair<ll, ll> b){ ll pay = a.first*b.second + a.second*b.first; ll payda = a.second*b.second; return mp(pay, payda); } pair<ll, ll> get(int i, ll pay, ll payda){ cout << "get(" << i << ", " << pay << ", " << payda << ")" << endl; /*double ans = presum[i][(int)(pay/payda)-1]; ans += mat[i][(int)(pay/payda)]*((pay/payda) - (int)(pay/payda)); return ans;*/ return sum(mp(presum[i][(pay/payda)-1], 1), mp((pay%payda)*mat[i][pay/payda], payda)); } pair<ll, ll> getmin(int i, pair<ll, ll> puan){ //cout << "getmin(" << i << ", " << puan.first << ", " << puan.second << ")" << endl; if (presum[i][m-1] < (double)puan.first/(double)puan.second) return mp(-1, -1); int l = -1; int r = m-1; while (l < r){ int m = (l+r+1)/2; if (presum[i][m] > (double)puan.first/(double)puan.second) r = m-1; else l = m; } //cout << bas(l) << endl; if (l != -1 && presum[i][l] == (double)puan.first/(double)puan.second) return mp(l+1, 1); puan = sum(puan, mp((l == -1) ? 0 : -presum[i][l], 1)); // mat[i][l+1]*oran = puan; return sum(mp(l+1, 1), mp(puan.first, puan.second*mat[i][l+1])); } int main(){ cin.tie(0); ios::sync_with_stdio(false); cin >> n >> m; for (int i = 0; i < n; i++){ ll cur = 0; for (int j = 0; j < m; j++){ cin >> mat[i][j]; cur += mat[i][j]; presum[i][j] = cur; } } for (int i = 0; i < n; i++){ for (int j = 0; j < n; j++){ bol[j][i] = getmin(i, mp(presum[i][m-1]*(j+1), n)); //cout << bol[i][j].first << ", " << bol[i][j].second << " "; } //cout << endl; } //cout << endl; bitset<2002> vis; vis.reset(); for (int i = 0; i < n; i++){ double minn = 1000000000; int mini = -1; for (int j = 0; j < n; j++){ if (vis[j]) continue; //cout << bas(i) << " " bas(j) << endl; //cout << bas(minn) << " " << bas(bol[i][j].first) << bas(bol[i][j].second) << endl; if ((double)bol[i][j].first / (double)bol[i][j].second < minn){ minn = (double)bol[i][j].first / (double)bol[i][j].second; mini = j; } } ans.pb(bol[i][mini]); p.pb(mini+1); vis[mini] = 1; } for (int i = 0; i < n-1; i++) cout << ans[i].first << " " << ans[i].second << endl; for (int i = 0; i < p.size(); i++) cout << p[i] << " "; }

Compilation message (stderr)

naan.cpp: In function 'int main()':
naan.cpp:97:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < p.size(); i++) cout << p[i] << " ";
                  ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...