제출 #243132

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
243132		osaaateiasavtnl	Naan (JOI19_naan)	C++14	0 / 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 len;
int cut[N];

int sum[N];

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

        int s = 0;            
        if (l / n == r / n) {
            s += (r - l + 1) * a[i][l/n];
        }   
        else {        
            int lj = l/n+1;
            int rj = r/n-1;

            s += (lj * n - l) * a[i][lj-1];
            s += (r - (rj + n - 1)) * a[i][rj+1];

            for (int j = lj; j <= rj; ++j)
                s += a[i][j] * n;
        }

        if (s >= sum[i])
            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];
        }
    }

    len = n * L;            

    int us = 0;
    for (int i = 0; i < n; ++i) {
        
        //cout << i << ' ' << us << endl;

        if (who(us, len - 1) == -1) {
            exit(1);
            cout << -1 << endl;
            exit(0);
        }   
    
        int l = us - 1;
        int r = len - 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;
    }   

    #ifdef HOME
    cout << "OK" << endl;
    #endif

    for (int i = 0; i < n - 1; ++i) {
        cout << cut[i] << ' ' << n << endl;
    }   

    for (int i = 0; i < n; ++i)
        cout << per[i]+1 << ' ';
    cout << endl;
}

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