Submission #1152783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152783		onbert	Naan (JOI19_naan)	C++20	29 / 100	57 ms	9032 KiB

naan

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2005, BIG = 1e9, INF = 1e18;
int n, m;
int a[maxn][maxn], sum[maxn][maxn], req[maxn];
bool vis[maxn];
signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int i=1;i<=n;i++) {
        int total = 0;
        for (int j=1;j<=m;j++) {
            cin >> a[i][j];
            sum[i][j] = sum[i][j-1] + a[i][j];
            total += a[i][j];
        }
        req[i] = (total * BIG + n - 1) / n;
    }
    int pos = 0;
    int ans[n+1];
    for (int i=1;i<=n;i++) {
        pair<int,int> mn = {INF, -1};
        int nxt = (pos + BIG - 1)/BIG, left = nxt * BIG - pos;
        for (int j=1;j<=n;j++) if (!vis[j]) {
            int l = pos+1, r = BIG * m;
            while (l < r) {
                int mid = (l+r)/2;
                int val;
                if (mid/BIG != pos/BIG) val = left * a[j][pos/BIG + 1] + (sum[j][mid/BIG] - sum[j][nxt]) * BIG + (mid%BIG) * a[j][mid/BIG + 1];
                else val = (mid - pos) * a[j][pos/BIG + 1];
                // cout << ".\n";
                // cout << j << " " << mid << " " << val << endl;
                // cout << left * a[j][pos/BIG + 1] << " " << (sum[j][mid/BIG] - sum[j][nxt]) * BIG << " " << (mid%BIG) * a[j][mid/BIG + 1] << endl;
                if (val >= req[j]) r = mid;
                else l = mid+1;
            }
            // return 0;
            mn = min(make_pair(l, j), mn);
            // cout << j << " " << l << endl;
        }
        ans[i] = mn.second;
        vis[mn.second] = true;
        pos = mn.first;
        // cout << pos << " " << BIG << "\n";
        if (i < n) cout << pos << " " << BIG << "\n";
    }
    for (int i=1;i<=n;i++) cout << ans[i] << " "; cout << "\n";
}

• Subtask 1: 5 / 5
• Subtask 2: 24 / 24
• Subtask 3: 0 / 71