oj.uz

Submission #117571

# Submission time Handle Problem Language Result Execution time Memory
117571 2019-06-16T15:32:21 Z duality Naan (JOI19_naan) C++11
29 / 100
 4000 ms 40048 KB 
#define DEBUG 0

#include <bits/stdc++.h>
using namespace std;

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------

int V[2000][2000];
LLI gcd(LLI a,LLI b) {
    LLI t;
    while (a > 0) t = b % a,b = a,a = t;
    return b;
}
struct frac {
    LLI n,d;
    frac reduce() {
        LLI g = gcd(n,d);
        n /= g,d /= g;
        return *this;
    }
    frac operator+(frac f) {
        return ((frac){n*f.d+d*f.n,d*f.d}).reduce();
    }
    frac operator-(frac f) {
        return ((frac){n*f.d-d*f.n,d*f.d}).reduce();
    }
    frac operator*(frac f) {
        return ((frac){n*f.n,d*f.d}).reduce();
    }
    bool operator<(frac f) {
        return (long double) n/d < (long double) f.n/f.d;
    }
};
int P[2000],done[2000];
LLI sum[2000][2001];
frac need[2000];
frac query(int i,frac a,frac b) {
    frac ans = (frac){0,1};
    ans = ans + (frac){sum[i][b.n/b.d],1};
    if ((b.n % b.d) != 0) ans = ans + (frac){V[i][b.n/b.d]*(b.n % b.d),b.d};
    ans = ans - (frac){sum[i][a.n/a.d],1};
    if ((a.n % a.d) != 0) ans = ans - (frac){V[i][a.n/a.d]*(a.n % a.d),a.d};
    return ans;
}
int main() {
    int i,j;
    int N,L;
    scanf("%d %d",&N,&L);
    for (i = 0; i < N; i++) {
        for (j = 0; j < L; j++) {
            scanf("%d",&V[i][j]);
            sum[i][j+1] = sum[i][j]+V[i][j];
        }
        need[i] = (frac){sum[i][L],N};
    }

    frac p = (frac){0,1};
    for (i = 0; i < N; i++) {
        frac best = (frac){L+1,1};
        int b = -1,d;
        for (j = 0; j < N; j++) {
            if (!done[j]) {
                int l = p.n/p.d,r = L;
                while (l < r) {
                    int m = (l+r) / 2;
                    if (query(j,p,(frac){m,1}) < need[j]) l = m+1;
                    else r = m;
                }
                //cout<<l<<endl;
                frac f = query(j,p,(frac){l,1});
                //cout<<f.n<<"/"<<f.d<<endl;
                f = f-need[j];
                f = f * (frac){1,V[j][l-1]};
                //cout<<f.n<<"/"<<f.d<<endl;
                frac q = ((frac){l,1})-f;
                if (q < best) best = q,b = j,d = V[j][l-1];
                //cout<<"q: "<<q.n<<"/"<<q.d<<endl;
            }
        }
        P[i] = b,done[b] = 1,p = best;
        if (p.d > N*d) {
            p.n = ((long double) p.n*(N*d)+p.d-1)/p.d;
            p.d = N*d,p.reduce();
        }
        if (i < N-1) printf("%lld %lld\n",(long long int) p.n,(long long int) p.d);
    }
    for (i = 0; i < N; i++) printf("%d ",P[i]+1);
    printf("\n");

    return 0;
}

Compilation message

naan.cpp: In function 'int main()':
naan.cpp:98: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:101:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&V[i][j]);
             ~~~~~^~~~~~~~~~~~~~~
naan.cpp:131:20: warning: 'd' may be used uninitialized in this function [-Wmaybe-uninitialized]
         if (p.d > N*d) {
                   ~^~

Subtask #1
5.0 / 5.0

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

Subtask #2
24.0 / 24.0

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

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 3 ms 384 KB Output is correct
19 Correct 3 ms 512 KB Output is correct
20 Correct 3 ms 512 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 2 ms 512 KB Output is correct
24 Correct 3 ms 512 KB Output is correct
25 Correct 2 ms 512 KB Output is correct
26 Correct 3 ms 384 KB Output is correct
27 Correct 2 ms 384 KB Output is correct
28 Correct 2 ms 384 KB Output is correct
29 Correct 3 ms 512 KB Output is correct
30 Correct 3 ms 512 KB Output is correct
31 Correct 3 ms 512 KB Output is correct
32 Correct 3 ms 512 KB Output is correct
33 Correct 3 ms 512 KB Output is correct
34 Correct 3 ms 512 KB Output is correct
35 Correct 4 ms 384 KB Output is correct
36 Correct 3 ms 512 KB Output is correct
37 Correct 3 ms 512 KB Output is correct
38 Correct 2 ms 384 KB Output is correct
39 Correct 3 ms 512 KB Output is correct
40 Correct 3 ms 384 KB Output is correct
41 Correct 2 ms 384 KB Output is correct
42 Correct 3 ms 512 KB Output is correct
43 Correct 837 ms 8140 KB Output is correct
44 Execution timed out 4026 ms 40048 KB Time limit exceeded
45 Halted 0 ms 0 KB -