Submission #203719

#TimeUsernameProblemLanguageResultExecution timeMemory
203719ics0503Naan (JOI19_naan)C++17
100 / 100
1096 ms188792 KiB
#include<stdio.h> #include<vector> #include<set> using namespace std; set<long long >people; long long v[2121][2121], S[2121][2121]; struct xy { long long x, y; }need[2121]; long long gcd(long long a, long long b) { if (b == 0)return a; return gcd(b, a%b); } struct xyz { long long x, y, z; void balance() { long long g = gcd(y, z); y /= g; z /= g; } }L[2121][2121]; bool cmp(xyz a, xyz b) { if (a.x != b.x) return a.x < b.x; return a.y * b.z < b.y * a.z; } vector<long long>ans; int main() { long long n, l, i, j; scanf("%lld%lld", &n, &l); for (i = 1; i <= n; i++)people.insert(i); for (i = 1; i <= n; i++) { L[i][0] = { 1,0,1 }; for (j = 1; j <= l; j++)scanf("%lld", &v[i][j]), S[i][j] = S[i][j - 1] + v[i][j],need[i].x+=v[i][j]; need[i].y = n; for (j = 1; j < n; j++) { L[i][j].x = L[i][j - 1].x; while (L[i][j].x<l && (S[i][L[i][j].x]) * need[i].y <= need[i].x * j) { L[i][j].x++; } L[i][j].y = need[i].x * j - S[i][L[i][j].x - 1] * need[i].y; L[i][j].z = v[i][L[i][j].x] * need[i].y; L[i][j].balance(); } } for (i = 1; i < n; i++) { xyz mn = { l + 1,0,1 }; long long mnw = 0; for (long long who : people) { if (cmp(L[who][i], mn)) { mn = L[who][i]; mnw = who; } } printf("%lld %lld\n", (mn.x - 1)*mn.z + mn.y, mn.z); people.erase(mnw); ans.push_back(mnw); } for (long long i = 0; i < ans.size(); i++)printf("%lld ", ans[i]); printf("%lld", *people.begin()); return 0; }

Compilation message (stderr)

naan.cpp: In function 'int main()':
naan.cpp:55:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (long long i = 0; i < ans.size(); i++)printf("%lld ", ans[i]);
                        ~~^~~~~~~~~~~~
naan.cpp:27:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  long long n, l, i, j; scanf("%lld%lld", &n, &l);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~
naan.cpp:31:83: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (j = 1; j <= l; j++)scanf("%lld", &v[i][j]), S[i][j] = S[i][j - 1] + v[i][j],need[i].x+=v[i][j];
                           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...