oj.uz

Submission #243561

# Submission time Handle Problem Language Result Execution time Memory
243561 2020-07-01T10:17:47 Z osaaateiasavtnl Naan (JOI19_naan) C++14
29 / 100
 104 ms 4728 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], 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.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 256 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 21 ms 384 KB Output is correct
12 Correct 8 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 7 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 512 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 4 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 5 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 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 6 ms 384 KB Output is correct
22 Correct 5 ms 512 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 6 ms 384 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 256 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 21 ms 384 KB Output is correct
12 Correct 8 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 7 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 512 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Correct 4 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 5 ms 384 KB Output is correct
31 Correct 5 ms 384 KB Output is correct
32 Correct 5 ms 384 KB Output is correct
33 Correct 5 ms 384 KB Output is correct
34 Correct 5 ms 384 KB Output is correct
35 Correct 5 ms 384 KB Output is correct
36 Correct 6 ms 384 KB Output is correct
37 Correct 5 ms 512 KB Output is correct
38 Correct 5 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 6 ms 384 KB Output is correct
43 Incorrect 104 ms 4728 KB Not a fair distribution.
44 Halted 0 ms 0 KB -