oj.uz

Submission #243573

# Submission time Handle Problem Language Result Execution time Memory
243573 2020-07-01T10:34:06 Z osaaateiasavtnl Naan (JOI19_naan) C++14
29 / 100
 687 ms 19432 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 = 1e18;
int n, L;
int v[N][N], sum[N];
 
int cost(int i, int l, int r, int step) {
    if (r < l)
        return 0;
 
    if (l < 0 || r >= L * step)
        exit(1);
 
    int lb = l/step;
    int rb = r/step;
    if (lb == rb)
        return (r - l + 1) * v[i][lb];
 
    int ans = v[i][lb] * (lb * step + step - l);
    ans += v[i][rb] * (r - rb * step + 1);
    for (int j = lb+1; j < rb; ++j)
        ans += v[i][j]*step;
    return ans;
}   
int mult(int a, int b) {
    if (a == 0 || b == 0)
        return 0;
    if (a > INF/b)
        return INF;
    else
        return a * b;
}   
int can(int l, int r, int step, vector <bool> used) {
    for (int i = 0; i < n; ++i) {
        if (used[i])
            continue;
        if (mult(cost(i, l, r, step), n) >= sum[i]*step)
            return i;
    }
    return -1;
}   
 
void solve(int step) {
    vector <int> cut(n-1), ord(n);
    vector <bool> used(n);
    int lf = 0;
    for (int add = 0; add < n; ++add) {
        if (can(lf, L * step - 1, step, used) == -1)
            return;
 
        int l = lf-1;
        int r = L * step - 1;
        while (l < r - 1) {
            int mid = (l + r) >> 1;
            if (can(lf, mid, step, used) == -1)
                l = mid;
            else
                r = mid;
        }   
 
        int who = can(lf, r, step, used);
        ord[add] = who;
        cut[add] = r;
        used[who] = 1;
        lf = r+1;
    }   
    
    for (auto e : cut)
        cout << e + 1 << ' ' << step << endl;
    for (auto e : ord)
        cout << e + 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 >> v[i][j];
            sum[i] += v[i][j];
        }
    }   
 
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < L; ++j) {
            solve(n * v[i][j]);
        }   
    }
 
    cout << -1 << endl;
}

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 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 6 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 16 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 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 6 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 5 ms 384 KB Output is correct
13 Correct 6 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 512 KB Output is correct
18 Correct 5 ms 512 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 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 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 6 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 16 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 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 6 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 5 ms 384 KB Output is correct
28 Correct 6 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 512 KB Output is correct
33 Correct 5 ms 512 KB Output is correct
34 Correct 5 ms 512 KB Output is correct
35 Correct 5 ms 384 KB Output is correct
36 Correct 5 ms 384 KB Output is correct
37 Correct 5 ms 384 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 5 ms 512 KB Output is correct
43 Correct 108 ms 4728 KB Output is correct
44 Incorrect 687 ms 19432 KB Not a fair distribution.
45 Halted 0 ms 0 KB -