oj.uz

Submission #699159

# Submission time Handle Problem Language Result Execution time Memory
699159 2023-02-15T22:12:14 Z doowey Naan (JOI19_naan) C++14
29 / 100
 40 ms 8992 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;

struct frac{
    ll A;
    ll B;
    frac operator+ (frac y){
        return {A * y.B + B * y.A, B * y.B};
    }
    frac operator- (frac y){
        return {A * y.B - B * y.A, B * y.B};
    }
    bool operator< (frac y){
        return (A * y.B - B * y.A < 0);
    }
};

ll V[N][N];
ll S[N][N];
int m;

frac calc(int id, frac P){
    int las = P.A / P.B;
    frac Y = {S[id][las], 1};
    frac add = (P - (frac){las, 1});
    add.A *= V[id][las + 1];
    Y = Y + add;
    return Y;
}

frac need[N];

int pi[N];

int main(){
    fastIO;
    //freopen("in.txt", "r", stdin);
    int n;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ){
        need[i] = {0, n};
        for(int j = 1; j <= m ; j ++ ){
            cin >> V[i][j];
            need[i].A += V[i][j];
            S[i][j] = V[i][j] + S[i][j - 1];
        }
        pi[i] = -1;
    }
    frac las = {0, 1};
    frac tis;
    frac nx;
    frac cur;
    frac low;
    int idx;
    frac S;
    ll X;
    for(int it = 1; it < n; it ++ ){
        low = {m, 1};
        idx = -1;
        for(int i = 1; i <= n; i ++ ){
            if(pi[i] == -1){
                tis = calc(i, las);
                for(int j = 1; j <= m; j ++ ){
                    nx = calc(i, {j, 1});
                    if(need[i] < nx - tis){
                        S = nx - tis;
                        S = S - need[i];
                        S.A *= (ll)n;
                        X = S.A / S.B;
                        tis = (frac){j, 1} - (frac){X, n * 1ll * V[i][j]};
                        if(tis < low){
                            low = tis;
                            idx = i;
                        }
                        break;
                    }
                }
            }
        }
        pi[idx] = it;
        las = low;
        cout << low.A << " " << low.B << "\n";
    }
    for(int i = 1; i <= n; i ++ ){
        if(pi[i] == -1) cout << n << " ";
        else cout << pi[i] << " ";
    }
    cout << "\n";
    return 0;
}

Compilation message

naan.cpp: In function 'int main()':
naan.cpp:63:10: warning: unused variable 'cur' [-Wunused-variable]
   63 |     frac cur;
      |          ^~~

Subtask #1
5.0 / 5.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 0 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 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 340 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 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 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 468 KB Output is correct

Subtask #3
0 / 71.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 0 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 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 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 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 468 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Correct 1 ms 468 KB Output is correct
32 Correct 1 ms 468 KB Output is correct
33 Correct 1 ms 468 KB Output is correct
34 Correct 1 ms 468 KB Output is correct
35 Correct 1 ms 468 KB Output is correct
36 Correct 1 ms 468 KB Output is correct
37 Correct 1 ms 468 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Correct 1 ms 468 KB Output is correct
40 Correct 1 ms 468 KB Output is correct
41 Correct 1 ms 340 KB Output is correct
42 Correct 1 ms 468 KB Output is correct
43 Incorrect 40 ms 8992 KB Not a fair distribution.
44 Halted 0 ms 0 KB -