Submission #243476

#	Time	Username	Problem	Language	Result	Execution time	Memory
243476		osaaateiasavtnl	Naan (JOI19_naan)	C++14	24 / 100	6 ms	512 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;
int n, L;
int a[N][N];
 
int per[N];
bool used[N];
 
int cut[N];
 
int sum[N]; 

int one = -1;
 
int who(int l, int r) {
    for (int i = 0; i < n; ++i) {
        if (used[i])
            continue;
 
        int s = 0;            

        if (l/one == r/one) {
            s += (r-l+1)*a[i][l/one];
        }   
        else {
            int lb = l/one;
            s += (one * (lb + 1) - l) * a[i][l/one];

            int rb = r/one;
            s += (r - rb * one + 1) * a[i][r/one];

            for (int j = lb+1; j < rb; ++j)
                s += a[i][j]*one;
        }   

        if (s * n >= sum[i] * one)
            return i;                    
    }   
    return -1;
}   
 
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 >> a[i][j];
            sum[i] += a[i][j];
        }
    }

    one = n * n * 60;

    int us = 0;
    for (int i = 0; i < n; ++i) {
        if (who(us, one * L - 1) == -1) {
            exit(1);
        }   
    
        int l = us - 1;
        int r = one * L - 1;
        while (l < r - 1) {
            int m = (l + r) >> 1;
            if (who(us, m) != -1)
                r = m;
            else
                l = m;
        }   
        int t = who(us, r);
        used[t] = 1;
        per[i] = t;
 
        cut[i] = r + 1;
        us = r + 1;
    }   
 
    for (int i = 0; i < n - 1; ++i) {
        cout << cut[i] << ' ' << one << endl;
    }   
 
    for (int i = 0; i < n; ++i)
        cout << per[i]+1 << ' ';
    cout << endl;
}

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