oj.uz

Submission #699126

# Submission time Handle Problem Language Result Execution time Memory
699126 2023-02-15T17:01:23 Z doowey Naan (JOI19_naan) C++14
5 / 100
 2 ms 340 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 2010;
ll V[N][N];

struct Frac{
    ll A;
    ll B;
}; // A / B

Frac add(Frac ai, Frac bi){
    return {(ai.A * 1ll * bi.B + bi.A * 1ll * ai.B), (ai.B * 1ll * bi.B)};
}

bool comp(Frac aa, Frac bb){
    bb.A = -bb.A;
    aa = add(aa, bb);
    if(aa.A >= 0){
        return true;
    }
    else{
        return false;
    }
}

int pip[N];
Frac need[N];
int ans[N];

int main(){
    fastIO;
    //freopen("in.txt", "r", stdin);
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ){
        need[i] = {0, n};
        for(int j = 0; j < m; j ++ ){
            cin >> V[i][j];
            need[i].A += V[i][j];
        }
        pip[i] = -1;
    }
    Frac las = {0ll, 1ll};
    Frac cum;
    Frac en;
    int id;
    int gi;
    ll C;
    ll X;
    Frac ee;
    vector<int> ord;
    for(int pos = 1; pos < n; pos ++ ){
        Frac low = {m,1};
        gi = -1;
        for(int chk = 1; chk <= n; chk ++ ){
            if(pip[chk] == -1){
                cum = {0ll, 1ll};
                id = las.A / las.B;
                cum = add({id+1, 1}, {-las.A, las.B});
                cum.A *= V[chk][id];
                while(id < m){
                    if(comp(cum, need[chk])){
                        break;
                    }
                    id ++ ;
                    cum = add(cum, {V[chk][id], 1});
                }
                C = n * V[chk][id];
                en = add(cum, {-need[chk].A, need[chk].B});
                en.A *= C;
                en.B *= V[chk][id];
                X = en.A / en.B;
                ee = add({id + 1, 1}, {-X,C});
                if(comp(low, ee)){
                    low = ee;
                    gi = chk;
                }
            }
        }
        cout << low.A << " " << low.B << "\n";
        las = low;
        pip[gi] = pos;
        ans[gi] = pos;
    }
    for(int i = 1; i <= n; i ++ ){
        if(pip[i] == -1) ans[i] = n;
    }
    for(int i = 1; i <= n; i ++ ){
        cout << ans[i] << " ";
    }
    cout << "\n";
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 2 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Incorrect 0 ms 340 KB Not a fair distribution.
24 Halted 0 ms 0 KB -

Subtask #3
0 / 71.0

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