oj.uz

Submission #243504

# Submission time Handle Problem Language Result Execution time Memory
243504 2020-07-01T09:15:29 Z osaaateiasavtnl Naan (JOI19_naan) C++14
29 / 100
 677 ms 19448 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, INF = 2e18;
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 > INF/n || s * n >= sum[i] * one)
            return i;                    
    }   
    return -1;
}   

void check(int x) {
    one = x;

    memset(used, 0, sizeof used);

    int us = 0;
    for (int i = 0; i < n; ++i) {
        if (who(us, one * L - 1) == -1) {
            return;
        }   
    
        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;

    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 >> 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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 20 ms 384 KB Output is correct
12 Correct 7 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 6 ms 384 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 6 ms 512 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 512 KB Output is correct
18 Correct 6 ms 512 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 512 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 4 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Correct 5 ms 512 KB Output is correct

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 20 ms 384 KB Output is correct
12 Correct 7 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 6 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 512 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Correct 5 ms 384 KB Output is correct
28 Correct 5 ms 384 KB Output is correct
29 Correct 5 ms 384 KB Output is correct
30 Correct 6 ms 512 KB Output is correct
31 Correct 5 ms 384 KB Output is correct
32 Correct 5 ms 512 KB Output is correct
33 Correct 6 ms 512 KB Output is correct
34 Correct 5 ms 384 KB Output is correct
35 Correct 5 ms 512 KB Output is correct
36 Correct 5 ms 384 KB Output is correct
37 Correct 5 ms 384 KB Output is correct
38 Correct 4 ms 384 KB Output is correct
39 Correct 5 ms 384 KB Output is correct
40 Correct 5 ms 384 KB Output is correct
41 Correct 5 ms 384 KB Output is correct
42 Correct 5 ms 512 KB Output is correct
43 Correct 104 ms 4728 KB Output is correct
44 Incorrect 677 ms 19448 KB Not a fair distribution.
45 Halted 0 ms 0 KB -