Submission #201366

#TimeUsernameProblemLanguageResultExecution timeMemory
201366BTheroNaan (JOI19_naan)C++17
0 / 100
5 ms424 KiB
// Why am I so dumb? :c // chrono::system_clock::now().time_since_epoch().count() #include<bits/stdc++.h> //#include<ext/pb_ds/assoc_container.hpp> //#include<ext/pb_ds/tree_policy.hpp> #define pb push_back #define mp make_pair #define all(x) (x).begin(), (x).end() #define fi first #define se second using namespace std; //using namespace __gnu_pbds; typedef long long ll; typedef pair<int, int> pii; //template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; const int MAXN = (int)2e3 + 5; struct Ratio { ll a, b; Ratio() { a = 0; b = 1; } Ratio(ll a, ll b) : a(a), b(b) {} }; bool operator < (Ratio f, Ratio s) { return f.a * s.b < f.b * s.a; } bool operator > (Ratio f, Ratio s) { return s < f; } bool operator == (Ratio f, Ratio s) { return !(f < s) && !(f > s); } bool operator <= (Ratio f, Ratio s) { return f < s || f == s; } bool operator >= (Ratio f, Ratio s) { return s <= f; } ll lcm(ll a, ll b) { return a / __gcd(a, b) * b; } Ratio operator + (Ratio f, Ratio s) { ll c = lcm(f.b, s.b); return Ratio(f.a * c / f.b + s.a * c / s.b, c); } void operator += (Ratio &f, Ratio s) { f = f + s; } vector<Ratio> V[MAXN]; ll arr[MAXN][MAXN]; bool used[MAXN]; int ptr[MAXN]; int n, m; void solve() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; ++i) { ll mean = 0, cur = 0; for (int j = 1; j <= m; ++j) { scanf("%lld", &arr[i][j]); mean += arr[i][j]; arr[i][j] *= n; } Ratio r(0, 1); for (int j = 1; j <= m; ++j) { ll X = arr[i][j]; while (X > 0) { if (cur + X > mean) { r += Ratio(mean - cur, arr[i][j]); X -= (mean - cur); cur = mean; } else { cur += X; r += Ratio(X, arr[i][j]); X = 0; } if (cur == mean) { V[i].pb(r); cur = 0; } } } assert(V[i].size() == n); } vector<int> perm; for (int j = 0; j < n; ++j) { int best = -1; for (int i = 1; i <= n; ++i) { if (!used[i]) { if (best == -1 || V[i][j] < V[best][j]) { best = i; } } } assert(best != -1); used[best] = 1; printf("%lld %lld\n", V[best][j].a, V[best][j].b); perm.pb(best); } for (int x : perm) { printf("%d ", x); } } int main() { int tt = 1; while (tt--) { solve(); } return 0; }

Compilation message (stderr)

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from naan.cpp:4:
naan.cpp: In function 'void solve()':
naan.cpp:115:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         assert(V[i].size() == n);                        
                ~~~~~~~~~~~~^~~~
naan.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
naan.cpp:86:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%lld", &arr[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...