oj.uz

Submission #209240

# Submission time Handle Problem Language Result Execution time Memory
209240 2020-03-13T13:13:05 Z coldEr66 Naan (JOI19_naan) C++14
29 / 100
 274 ms 14072 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double lf;
typedef pair<ll,ll> ii;
typedef pair<ii,int> iii;
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define RST(i,n) memset(i,n,sizeof i)
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(),a.end()
#define X first
#define Y second
#define eb emplace_back
#ifdef cold66
#define debug(...) do{\
    fprintf(stderr,"%d (%s) = ",__LINE__,#__VA_ARGS__);\
    _do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<", ";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
    _s<<"{";
    for(It _it=_ita;_it!=_itb;_it++)
    {
        _s<<(_it==_ita?"":",")<<*_it;
    }
    _s<<"}";
    return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
#else
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#endif // cold66
//}
template<class T> inline bool chkmax(T &a, const T &b) { return b > a ? a = b, true : false; }
template<class T> inline bool chkmin(T &a, const T &b) { return b < a ? a = b, true : false; }

const ll MAXn=2e3+5,MAXlg=__lg(MAXn)+2;
const ll MOD=1000000007;
const ll INF=0x3f3f3f3f;

ll n,l;
ii v[MAXn][MAXn];
ii cut[MAXn][MAXn];
vector<ii> ans;
ll ansp[MAXn];
bool ok[MAXn];
ii d[MAXn];
bool cmp(const iii &a,const iii &b){
    __int128 xx = a.X.X * b.X.Y, yy = a.X.Y * b.X.X;
    return xx < yy;
}
bool operator <= (const ii &a,const ii &b) {
    __int128 xx = a.X * b.Y, yy = a.Y * b.X;
    return xx <= yy;
}
ii operator - (const ii a,const ii b) {
    if (a.Y != b.Y) {
        __int128 xx = a.X*b.Y, yy = a.Y*b.X, zz = a.Y*b.Y;
        __int128 gcd = __gcd(a.Y,b.Y);
        xx /= gcd, yy /= gcd, zz /= gcd;
        ii ret = ii(xx - yy,zz);
        return ret;
    }
    else {
        ll gcd = __gcd(a.X - b.X,a.Y);
        ii ret = ii(a.X - b.X,a.Y);
        ret.X /= gcd, ret.Y /= gcd;
        return ii(a.X - b.X,a.Y);
    }
}
ii operator + (const ii &a,const ii &b){
    if (a.Y != b.Y) {
        __int128 xx = a.X*b.Y, yy = a.Y*b.X, zz = a.Y*b.Y;
        __int128 gcd = __gcd(a.Y,b.Y);
        xx /= gcd, yy /= gcd, zz /= gcd;
        ii ret = ii(xx + yy,zz);
        return ret;
    }
    else {
        ll gcd = __gcd(a.X + b.X,a.Y);
        ii ret = ii(a.X + b.X,a.Y);
        ret.X /= gcd, ret.Y /= gcd;
        return ii(a.X + b.X,a.Y);
    }
}
ii divi(ii a,ii b){
    __int128 xx = a.X * b.Y, yy = a.Y * b.X;
    __int128 gcd = __gcd(xx,yy);
    xx /= gcd, yy /= gcd;
    ii ret = ii(xx,yy);
    return ret;
}
void build(ll x,ll sum) {
    debug(x,sum);
    ll idx = 0;
    ii tmp = ii(0,1);
    ii c = ii(sum/n,1);
    ii cur = ii(0,1);
    REP (i,l) d[i] = v[x][i];
    REP (i,n-1) {
        cur = ii(0,1);
        tmp = ii(0,1);
        while (idx < l && tmp+d[idx] <= c) {
            tmp = tmp + d[idx];
            cur = cur + divi(d[idx],v[x][idx]);
            idx++;
        }
        ii need = c - tmp;
        cur = cur + divi(need,v[x][idx]);
        debug(tmp,need);
        ll gcd = __gcd(cur.X,cur.Y);
        cur.X /= gcd, cur.Y /= gcd;
        if (!i) cut[x][i] = cur;
        else cut[x][i] = cut[x][i-1] + cur;
        d[idx] = d[idx] - need;
        debug(v[x][idx]);
    }
}
int main(){
    IOS();
    cin >> n >> l;
    REP (i,n) {
        ll tmp = 0;
        REP (j,l) {
            cin >> v[i][j].X;
            v[i][j].X *= n;
            v[i][j].Y = 1;
            tmp += v[i][j].X;
        }
        build(i,tmp);
    }

    REP (j,n-1) {
        vector<iii> tmp;
        REP (i,n) {
            if (ok[i]) continue;
            tmp.eb(cut[i][j],i);
        }
        sort(ALL(tmp),cmp);
        debug(tmp);
        ll id = tmp[0].Y;
        ok[id] = true;
        ans.eb(tmp[0].X);
        ansp[j] = id;
    }
    REP (i,n) if (!ok[i]) ansp[n-1] = i;
    REP (i,n-1) {
        ll gcd = __gcd(ans[i].X,ans[i].Y);
        ans[i].X /= gcd, ans[i].Y /= gcd;
        cout << ans[i].X << ' ' << ans[i].Y << endl;
    }
    REP (i,n) cout << ansp[i] + 1 << " \n"[i==n-1];
}

Subtask #1
5.0 / 5.0

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

Subtask #2
24.0 / 24.0

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

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 504 KB Output is correct
12 Correct 5 ms 508 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 504 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 504 KB Output is correct
18 Correct 5 ms 504 KB Output is correct
19 Correct 6 ms 504 KB Output is correct
20 Correct 6 ms 504 KB Output is correct
21 Correct 5 ms 504 KB Output is correct
22 Correct 5 ms 504 KB Output is correct
23 Correct 5 ms 504 KB Output is correct
24 Correct 6 ms 632 KB Output is correct
25 Correct 6 ms 632 KB Output is correct
26 Correct 5 ms 504 KB Output is correct
27 Correct 4 ms 376 KB Output is correct
28 Correct 5 ms 504 KB Output is correct
29 Correct 6 ms 632 KB Output is correct
30 Correct 6 ms 504 KB Output is correct
31 Correct 6 ms 632 KB Output is correct
32 Correct 6 ms 632 KB Output is correct
33 Correct 6 ms 632 KB Output is correct
34 Correct 6 ms 628 KB Output is correct
35 Correct 7 ms 632 KB Output is correct
36 Correct 8 ms 632 KB Output is correct
37 Correct 6 ms 632 KB Output is correct
38 Correct 5 ms 376 KB Output is correct
39 Correct 6 ms 504 KB Output is correct
40 Correct 5 ms 504 KB Output is correct
41 Correct 5 ms 504 KB Output is correct
42 Correct 5 ms 504 KB Output is correct
43 Incorrect 274 ms 14072 KB Integer parameter [name=A_i] equals to -176733634823, violates the range [1, 2000000000000]
44 Halted 0 ms 0 KB -