oj.uz

Submission #243468

# Submission time Handle Problem Language Result Execution time Memory
243468 2020-07-01T08:40:15 Z osaaateiasavtnl Naan (JOI19_naan) C++14
0 / 100
 4000 ms 632 KB 
#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;            

        for (int j = l; j <= r; ++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 * L;

    int us = 0;
    for (int i = 0; i < n; ++i) {
        
        //cout << i << ' ' << us << endl;
 
        if (who(us, one * L - 1) == -1) {
            exit(1);
            cout << -1 << endl;
            exit(0);
        }   
    
        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;
    }   
 
    #ifdef HOME
    cout << "OK" << endl;
    #endif
 
    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.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 1081 ms 632 KB Output is correct
3 Correct 1312 ms 504 KB Output is correct
4 Correct 1540 ms 580 KB Output is correct
5 Correct 508 ms 436 KB Output is correct
6 Correct 17 ms 384 KB Output is correct
7 Correct 885 ms 444 KB Output is correct
8 Correct 657 ms 472 KB Output is correct
9 Correct 35 ms 384 KB Output is correct
10 Correct 1180 ms 436 KB Output is correct
11 Runtime error 907 ms 444 KB Execution failed because the return code was nonzero
12 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 600 ms 516 KB Output is correct
2 Correct 1856 ms 476 KB Output is correct
3 Correct 3196 ms 504 KB Output is correct
4 Execution timed out 4069 ms 496 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 1081 ms 632 KB Output is correct
3 Correct 1312 ms 504 KB Output is correct
4 Correct 1540 ms 580 KB Output is correct
5 Correct 508 ms 436 KB Output is correct
6 Correct 17 ms 384 KB Output is correct
7 Correct 885 ms 444 KB Output is correct
8 Correct 657 ms 472 KB Output is correct
9 Correct 35 ms 384 KB Output is correct
10 Correct 1180 ms 436 KB Output is correct
11 Runtime error 907 ms 444 KB Execution failed because the return code was nonzero
12 Halted 0 ms 0 KB -