Submission #243561

#	Time	Username	Problem	Language	Result	Execution time	Memory
243561		osaaateiasavtnl	Naan (JOI19_naan)	C++14	29 / 100	104 ms	4728 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 = 2e18;
int n, L;
int a[N][N], sum[N]; 
 
int mult(int a, int b) {
    if (a == 0 || b == 0)
        return 0;
    if (a > INF/b)
        return INF;
    else
        return a * b;
}   
 
int cost(int i, int l, int r, int one) {
    if (r < l)
        return 0;
 
    if (l/one == r/one) {
        return (r - l + 1) * a[i][l/one];
    }   
 
    int ans = 0;
 
    int lb = l/one;
    ans += (lb * one + one - l) * a[i][l/one];
 
    int rb = r/one;
    ans += (r - rb * one + 1) * a[i][r/one];
 
    for (int j = lb+1; j < rb; ++j)
        ans += a[i][j]*one;
 
    if (ans > 1e17)
        exit(1);
 
    return ans;
}   
 
int who(int l, int r, int one, const vector <bool> &used) {
    for (int i = 0; i < n; ++i) {
        if (used[i])
            continue;
        if (mult(cost(i, l, r, one), n) >= sum[i] * one) {
            return i;            
        }   
    }               
    return -1;
}
 
void check(int one) {
    if (one > 1000 * 1000 * 1000)
        exit(1);
 
    vector <int> cut(n-1), per(n);
    vector <bool> used(n);
    int ptr = 0;
    for (int t = 0; t < n; ++t) {
        if (who(ptr, L * one - 1, one, used) == -1)
            return;
 
        int l = ptr - 1;
        int r = L * one - 1;
        while (l < r - 1) {
            int m = (l + r) >> 1;
            if (who(ptr, m, one, used) == -1)
                l = m;
            else
                r = m;
        }   
 
        if (t < n - 1) {
            cut[t] = r+1;
        }
 
        int num = who(ptr, r, one, used);
        per[num] = t+1;
        used[num] = 1;        
 
        ptr = r+1;
    }   
 
    #ifdef HOME
    cout << "one : " << one << endl;
 
    for (auto e : cut)
        cout << e << ' ';
    cout << endl;
 
    for (auto e : per)
        cout << e << ' ';
    cout << endl;
    #endif
 
    for (int i = 0; i < n; ++i) {
        int p = per[i]-1;
 
        int l = 0;
        if (p)
            l = cut[p-1];
 
        int r = L * one - 1;
        if (p < n - 1)
            r = cut[p]-1;
        
        if (mult(cost(i, l, r, one), n) < sum[i]*n) {
            exit(1);
        }
    }   
 
    if (cut.size() && cut[0] <= 0) {
        exit(1);
    }   
    for (int i = 0; i + 1 < n - 1; ++i) {
        if (cut[i] >= cut[i+1]) {
            exit(1);
        }   
    }   
    if (cut.size() && cut.back() >= L * one) {
        exit(1);
    }   

    for (int i = 0; i < n - 1; ++i) 
        cout << cut[i] << ' ' << one << endl;
    for (auto e : per)
        cout << e << ' ';
    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;

    if (n == 1)
        exit(1);

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < L; ++j) {
            cin >> a[i][j];
            sum[i] += a[i][j];
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < L; ++j) {
            check(n * a[i][j]);
        }   
    }
    
    exit(1);
}

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