Submission #243572

#	Time	Username	Problem	Language	Result	Execution time	Memory
243572		osaaateiasavtnl	Naan (JOI19_naan)	C++14	29 / 100	694 ms	19392 KiB

naan

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
#define debug(x) std::cout << #x << ": " << x << '\n';

const int N = 2007, INF = 1e18;
int n, L;
int v[N][N], sum[N];

int cost(int i, int l, int r, int step) {
    if (r < l)
        return 0;

    if (l < 0 || r >= L * step)
        exit(1);

    int lb = l/step;
    int rb = r/step;
    if (lb == rb)
        return (r - l + 1) * v[i][lb];

    int ans = v[i][lb] * (lb * step + step - l);
    ans += v[i][rb] * (r - rb * step + 1);
    for (int j = lb+1; j < rb; ++j)
        ans += v[i][j]*step;
    return ans;
}   
int mult(int a, int b) {
    if (a == 0 || b == 0)
        return 0;
    if (a > INF/b)
        return INF;
    else
        return a * b;
}   
int can(int l, int r, int step, vector <bool> used) {
    for (int i = 0; i < n; ++i) {
        if (used[i])
            continue;
        if (mult(cost(i, l, r, step), n) >= sum[i]*step)
            return i;
    }
    return -1;
}   

void solve(int step) {
    vector <int> cut(n-1), ord(n);
    vector <bool> used(n);
    int lf = 0;
    for (int add = 0; add < n; ++add) {
        if (can(lf, L * step - 1, step, used) == -1)
            return;

        int l = lf-1;
        int r = L * step - 1;
        while (l < r - 1) {
            int mid = (l + r) >> 1;
            if (can(lf, mid, step, used) == -1)
                l = mid;
            else
                r = mid;
        }   

        int who = can(lf, r, step, used);
        ord[add] = who;
        cut[add] = r;
        used[who] = 1;
        lf = r+1;
    }   
    
    for (auto e : cut)
        cout << e + 1 << ' ' << step << endl;
    for (auto e : ord)
        cout << e + 1 << ' ';
    cout << endl;
    exit(0);
}   

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif

    cin >> n >> L;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < L; ++j) {
            cin >> v[i][j];
            sum[i] += v[i][j];
        }
    }   

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < L; ++j) {
            solve(n * v[i][j]);
        }   
    }

    exit(1);
}

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