oj.uz

Submission #123869

# Submission time Handle Problem Language Result Execution time Memory
123869 2019-07-02T08:19:35 Z 송준혁(#3032) Naan (JOI19_naan) C++14
29 / 100
 4 ms 764 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int N, K=1, L;

struct Rat{
    LL p=1, q=0;

    Rat(){}
    Rat(LL x, LL y){
        p = y, q = x;
    }

    Rat operator+(const Rat &r)const{
        return Rat(q*r.p + r.q*p, p*r.p);
    }
    Rat operator-(const Rat &r)const{
        return Rat(q*r.p - r.q*p, p*r.p);
    }
    Rat operator*(const Rat &r)const{
        return Rat(q*r.q, p*r.p);
    }
    Rat operator/(const Rat &r)const{
        return Rat(q*r.p, p*r.q);
    }
    bool operator<(const Rat &r)const{
        return q*r.p < r.q*p;
    }
} A[10][2020];

int main(){
    scanf("%d %d", &N, &L);
    for (int i=1; i<=N; i++) {
        for (int j=1; j<=L; j++) {
            scanf("%lld", &A[i][j].q);
            A[i][0] = A[i][0] + A[i][j];
        }
        A[i][0].p = N;
    }
    vector<int> P;
    for (int i=1; i<=N; i++) P.push_back(i);
    for (int i=1; i<=N; i++) K *= i;
    while (K--){
        Rat R;
        R.p=1, R.q=0;
        bool tf = true;
        for (int i=0; i<N; i++){
            Rat S = A[P[i]][0];
            while (R < (Rat){L, 1}){
                Rat x = A[P[i]][R.q/R.p+1] * (Rat(R.q/R.p+1, 1) - R);
                if (x < S){
                    S = S - x;
                    R.q = R.q/R.p+1;
                    R.p = 1;
                }
                else{
                    R = R + (S / A[P[i]][R.q/R.p+1]);
                    S = Rat(0, 1);
                    break;
                }
            }
            if (Rat(0, 1) < S) {
                tf = false;
                break;
            }
        }
        if (tf) break;
        next_permutation(P.begin(), P.end());
    }

    Rat R;
    R.p=1, R.q=0;
    for (int i=0; i<N-1; i++){
        Rat S = A[P[i]][0];
        while (R < (Rat){L, 1}){
            Rat x = A[P[i]][R.q/R.p+1] * (Rat(R.q/R.p+1, 1) - R);
            if (x < S){
                S = S - x;
                R.q = R.q/R.p+1;
                R.p = 1;
            }
            else{
                R = R + (S / A[P[i]][R.q/R.p+1]);
                S = Rat(0, 1);
                break;
            }
        }
        printf("%lld %lld\n", R.q, R.p);
    }
    for (int i=0; i<N; i++) printf("%d ", P[i]);
    return 0;
}

Compilation message

naan.cpp: In function 'int main()':
naan.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &L);
     ~~~~~^~~~~~~~~~~~~~~~~
naan.cpp:37:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%lld", &A[i][j].q);
             ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
24.0 / 24.0

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

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 3 ms 692 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Correct 3 ms 632 KB Output is correct
11 Correct 3 ms 632 KB Output is correct
12 Correct 3 ms 632 KB Output is correct
13 Correct 3 ms 632 KB Output is correct
14 Correct 3 ms 632 KB Output is correct
15 Correct 3 ms 632 KB Output is correct
16 Correct 3 ms 632 KB Output is correct
17 Correct 3 ms 632 KB Output is correct
18 Correct 3 ms 632 KB Output is correct
19 Correct 3 ms 632 KB Output is correct
20 Correct 3 ms 604 KB Output is correct
21 Correct 3 ms 764 KB Output is correct
22 Correct 2 ms 632 KB Output is correct
23 Correct 2 ms 632 KB Output is correct
24 Correct 3 ms 632 KB Output is correct
25 Correct 3 ms 632 KB Output is correct
26 Correct 3 ms 632 KB Output is correct
27 Correct 2 ms 632 KB Output is correct
28 Correct 3 ms 632 KB Output is correct
29 Correct 4 ms 632 KB Output is correct
30 Correct 3 ms 632 KB Output is correct
31 Correct 3 ms 632 KB Output is correct
32 Correct 3 ms 632 KB Output is correct
33 Correct 3 ms 632 KB Output is correct
34 Correct 3 ms 632 KB Output is correct
35 Correct 3 ms 632 KB Output is correct
36 Correct 3 ms 632 KB Output is correct
37 Correct 3 ms 632 KB Output is correct
38 Correct 2 ms 632 KB Output is correct
39 Correct 3 ms 548 KB Output is correct
40 Correct 3 ms 632 KB Output is correct
41 Correct 2 ms 632 KB Output is correct
42 Correct 3 ms 632 KB Output is correct
43 Incorrect 3 ms 632 KB Unexpected end of file - int64 expected
44 Halted 0 ms 0 KB -