Submission #117567

#	Time	Username	Problem	Language	Result	Execution time	Memory
117567		duality	Naan (JOI19_naan)	C++11	Compilation error	0 ms	0 KiB

naan

#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 __int128;
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 > 1e9) {
            p.n = ((long double) p.n*1e9+p.d-1)/p.d;
            p.d = 1e9,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 (stderr)

naan.cpp:46:23: error: multiple types in one declaration
 typedef long long int __int128;
                       ^~~~~~~~
naan.cpp:46:23: error: declaration does not declare anything [-fpermissive]
naan.cpp:50:14: error: 'LLI' was not declared in this scope
 typedef pair<LLI,LLI> plli;
              ^~~
naan.cpp:50:14: note: suggested alternative: 'ULLI'
 typedef pair<LLI,LLI> plli;
              ^~~
              ULLI
naan.cpp:50:18: error: 'LLI' was not declared in this scope
 typedef pair<LLI,LLI> plli;
                  ^~~
naan.cpp:50:18: note: suggested alternative: 'ULLI'
 typedef pair<LLI,LLI> plli;
                  ^~~
                  ULLI
naan.cpp:50:21: error: template argument 1 is invalid
 typedef pair<LLI,LLI> plli;
                     ^
naan.cpp:50:21: error: template argument 2 is invalid
naan.cpp:52:16: error: 'LLI' was not declared in this scope
 typedef vector<LLI> vlli;
                ^~~
naan.cpp:52:16: note: suggested alternative: 'ULLI'
 typedef vector<LLI> vlli;
                ^~~
                ULLI
naan.cpp:52:19: error: template argument 1 is invalid
 typedef vector<LLI> vlli;
                   ^
naan.cpp:52:19: error: template argument 2 is invalid
naan.cpp:59:1: error: 'LLI' does not name a type; did you mean 'ULLI'?
 LLI gcd(LLI a,LLI b) {
 ^~~
 ULLI
naan.cpp:65:5: error: 'LLI' does not name a type; did you mean 'ULLI'?
     LLI n,d;
     ^~~
     ULLI
naan.cpp: In member function 'frac frac::reduce()':
naan.cpp:67:9: error: 'LLI' was not declared in this scope
         LLI g = gcd(n,d);
         ^~~
naan.cpp:67:9: note: suggested alternative: 'ULLI'
         LLI g = gcd(n,d);
         ^~~
         ULLI
naan.cpp:68:9: error: 'n' was not declared in this scope
         n /= g,d /= g;
         ^
naan.cpp:68:14: error: 'g' was not declared in this scope
         n /= g,d /= g;
              ^
naan.cpp:68:16: error: 'd' was not declared in this scope
         n /= g,d /= g;
                ^
naan.cpp: In member function 'frac frac::operator+(frac)':
naan.cpp:72:24: error: 'n' was not declared in this scope
         return ((frac){n*f.d+d*f.n,d*f.d}).reduce();
                        ^
naan.cpp:72:28: error: 'struct frac' has no member named 'd'
         return ((frac){n*f.d+d*f.n,d*f.d}).reduce();
                            ^
naan.cpp:72:30: error: 'd' was not declared in this scope
         return ((frac){n*f.d+d*f.n,d*f.d}).reduce();
                              ^
naan.cpp:72:34: error: 'struct frac' has no member named 'n'
         return ((frac){n*f.d+d*f.n,d*f.d}).reduce();
                                  ^
naan.cpp:72:40: error: 'struct frac' has no member named 'd'
         return ((frac){n*f.d+d*f.n,d*f.d}).reduce();
                                        ^
naan.cpp: In member function 'frac frac::operator-(frac)':
naan.cpp:75:24: error: 'n' was not declared in this scope
         return ((frac){n*f.d-d*f.n,d*f.d}).reduce();
                        ^
naan.cpp:75:28: error: 'struct frac' has no member named 'd'
         return ((frac){n*f.d-d*f.n,d*f.d}).reduce();
                            ^
naan.cpp:75:30: error: 'd' was not declared in this scope
         return ((frac){n*f.d-d*f.n,d*f.d}).reduce();
                              ^
naan.cpp:75:34: error: 'struct frac' has no member named 'n'
         return ((frac){n*f.d-d*f.n,d*f.d}).reduce();
                                  ^
naan.cpp:75:40: error: 'struct frac' has no member named 'd'
         return ((frac){n*f.d-d*f.n,d*f.d}).reduce();
                                        ^
naan.cpp: In member function 'frac frac::operator*(frac)':
naan.cpp:78:24: error: 'n' was not declared in this scope
         return ((frac){n*f.n,d*f.d}).reduce();
                        ^
naan.cpp:78:28: error: 'struct frac' has no member named 'n'
         return ((frac){n*f.n,d*f.d}).reduce();
                            ^
naan.cpp:78:30: error: 'd' was not declared in this scope
         return ((frac){n*f.n,d*f.d}).reduce();
                              ^
naan.cpp:78:34: error: 'struct frac' has no member named 'd'
         return ((frac){n*f.n,d*f.d}).reduce();
                                  ^
naan.cpp: In member function 'bool frac::operator<(frac)':
naan.cpp:81:30: error: 'n' was not declared in this scope
         return (long double) n/d < (long double) f.n/f.d;
                              ^
naan.cpp:81:32: error: 'd' was not declared in this scope
         return (long double) n/d < (long double) f.n/f.d;
                                ^
naan.cpp:81:52: error: 'struct frac' has no member named 'n'
         return (long double) n/d < (long double) f.n/f.d;
                                                    ^
naan.cpp:81:56: error: 'struct frac' has no member named 'd'
         return (long double) n/d < (long double) f.n/f.d;
                                                        ^
naan.cpp: At global scope:
naan.cpp:85:1: error: 'LLI' does not name a type; did you mean 'ULLI'?
 LLI sum[2000][2001];
 ^~~
 ULLI
naan.cpp: In function 'frac query(int, frac, frac)':
naan.cpp:88:26: error: too many initializers for 'frac'
     frac ans = (frac){0,1};
                          ^
naan.cpp:89:24: error: 'sum' was not declared in this scope
     ans = ans + (frac){sum[i][b.n/b.d],1};
                        ^~~
naan.cpp:89:33: error: 'struct frac' has no member named 'n'
     ans = ans + (frac){sum[i][b.n/b.d],1};
                                 ^
naan.cpp:89:37: error: 'struct frac' has no member named 'd'
     ans = ans + (frac){sum[i][b.n/b.d],1};
                                     ^
naan.cpp:90:12: error: 'struct frac' has no member named 'n'
     if ((b.n % b.d) != 0) ans = ans + (frac){V[i][b.n/b.d]*(b.n % b.d),b.d};
            ^
naan.cpp:90:18: error: 'struct frac' has no member named 'd'
     if ((b.n % b.d) != 0) ans = ans + (frac){V[i][b.n/b.d]*(b.n % b.d),b.d};
                  ^
naan.cpp:90:53: error: 'struct frac' has no member named 'n'
     if ((b.n % b.d) != 0) ans = ans + (frac){V[i][b.n/b.d]*(b.n % b.d),b.d};
                                                     ^
naan.cpp:90:57: error: 'struct frac' has no member named 'd'
     if ((b.n % b.d) != 0) ans = ans + (frac){V[i][b.n/b.d]*(b.n % b.d),b.d};
                                                         ^
naan.cpp:90:63: error: 'struct frac' has no member named 'n'
     if ((b.n % b.d) != 0) ans = ans + (frac){V[i][b.n/b.d]*(b.n % b.d),b.d};
                                                               ^
naan.cpp:90:69: error: 'struct frac' has no member named 'd'
     if ((b.n % b.d) != 0) ans = ans + (frac){V[i][b.n/b.d]*(b.n % b.d),b.d};
                                                                     ^
naan.cpp:90:74: error: 'struct frac' has no member named 'd'
     if ((b.n % b.d) != 0) ans = ans + (frac){V[i][b.n/b.d]*(b.n % b.d),b.d};
                                                                          ^
naan.cpp:91:33: error: 'struct frac' has no member named 'n'
     ans = ans - (frac){sum[i][a.n/a.d],1};
                                 ^
naan.cpp:91:37: error: 'struct frac' has no member named 'd'
     ans = ans - (frac){sum[i][a.n/a.d],1};
                                     ^
naan.cpp:92:12: error: 'struct frac' has no member named 'n'
     if ((a.n % a.d) != 0) ans = ans - (frac){V[i][a.n/a.d]*(a.n % a.d),a.d};
            ^
naan.cpp:92:18: error: 'struct frac' has no member named 'd'
     if ((a.n % a.d) != 0) ans = ans - (frac){V[i][a.n/a.d]*(a.n % a.d),a.d};
                  ^
naan.cpp:92:53: error: 'struct frac' has no member named 'n'
     if ((a.n % a.d) != 0) ans = ans - (frac){V[i][a.n/a.d]*(a.n % a.d),a.d};
                                                     ^
naan.cpp:92:57: error: 'struct frac' has no member named 'd'
     if ((a.n % a.d) != 0) ans = ans - (frac){V[i][a.n/a.d]*(a.n % a.d),a.d};
                                                         ^
naan.cpp:92:63: error: 'struct frac' has no member named 'n'
     if ((a.n % a.d) != 0) ans = ans - (frac){V[i][a.n/a.d]*(a.n % a.d),a.d};
                                                               ^
naan.cpp:92:69: error: 'struct frac' has no member named 'd'
     if ((a.n % a.d) != 0) ans = ans - (frac){V[i][a.n/a.d]*(a.n % a.d),a.d};
                                                                     ^
naan.cpp:92:74: error: 'struct frac' has no member named 'd'
     if ((a.n % a.d) != 0) ans = ans - (frac){V[i][a.n/a.d]*(a.n % a.d),a.d};
                                                                          ^
naan.cpp: In function 'int main()':
naan.cpp:102:13: error: 'sum' was not declared in this scope
             sum[i][j+1] = sum[i][j]+V[i][j];
             ^~~
naan.cpp:104:26: error: 'sum' was not declared in this scope
         need[i] = (frac){sum[i][L],N};
                          ^~~
naan.cpp:107:24: error: too many initializers for 'frac'
     frac p = (frac){0,1};
                        ^
naan.cpp:109:33: error: too many initializers for 'frac'
         frac best = (frac){L+1,1};
                                 ^
naan.cpp:113:27: error: 'struct frac' has no member named 'n'
                 int l = p.n/p.d,r = L;
                           ^
naan.cpp:113:31: error: 'struct frac' has no member named 'd'
                 int l = p.n/p.d,r = L;
                               ^
naan.cpp:114:28: error: 'r' was not declared in this scope
                 while (l < r) {
                            ^
naan.cpp:116:45: error: too many initializers for 'frac'
                     if (query(j,p,(frac){m,1}) < need[j]) l = m+1;
                                             ^
naan.cpp:120:46: error: too many initializers for 'frac'
                 frac f = query(j,p,(frac){l,1});
                                              ^
naan.cpp:123:43: error: too many initializers for 'frac'
                 f = f * (frac){1,V[j][l-1]};
                                           ^
naan.cpp:125:37: error: too many initializers for 'frac'
                 frac q = ((frac){l,1})-f;
                                     ^
naan.cpp:131:15: error: 'struct frac' has no member named 'd'
         if (p.d > 1e9) {
               ^
naan.cpp:132:15: error: 'struct frac' has no member named 'n'
             p.n = ((long double) p.n*1e9+p.d-1)/p.d;
               ^
naan.cpp:132:36: error: 'struct frac' has no member named 'n'
             p.n = ((long double) p.n*1e9+p.d-1)/p.d;
                                    ^
naan.cpp:132:44: error: 'struct frac' has no member named 'd'
             p.n = ((long double) p.n*1e9+p.d-1)/p.d;
                                            ^
naan.cpp:132:51: error: 'struct frac' has no member named 'd'
             p.n = ((long double) p.n*1e9+p.d-1)/p.d;
                                                   ^
naan.cpp:133:15: error: 'struct frac' has no member named 'd'
             p.d = 1e9,p.reduce();
               ^
naan.cpp:135:61: error: 'struct frac' has no member named 'n'
         if (i < N-1) printf("%lld %lld\n",(long long int) p.n,(long long int) p.d);
                                                             ^
naan.cpp:135:81: error: 'struct frac' has no member named 'd'
         if (i < N-1) printf("%lld %lld\n",(long long int) p.n,(long long int) p.d);
                                                                                 ^
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]);
             ~~~~~^~~~~~~~~~~~~~~