Submission #209272

#	Time	Username	Problem	Language	Result	Execution time	Memory
209272		coldEr66	Naan (JOI19_naan)	C++14	29 / 100	299 ms	14072 KiB

naan

#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 operator <= (const ii &a,const ii &b) {
    __int128 xx = (__int128)a.X * b.Y, yy = (__int128)a.Y * b.X;
    return xx <= yy;
}
bool operator < (const ii &a,const ii &b) {
    __int128 xx = (__int128)a.X * b.Y, yy = (__int128)a.Y * b.X;
    return xx < yy;
}
ii operator - (const ii a,const ii b) {
    if (a.Y != b.Y) {
        __int128 xx = (__int128)a.X*b.Y, yy = (__int128)a.Y*b.X, zz = (__int128)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 {
        __int128 xx = __int128(a.X - b.X), yy = __int128(a.Y);
        __int128 gcd = __gcd(xx,yy);
        xx /= gcd, yy /= gcd;
        ii ret = ii(xx,yy);
        return ret;
    }
}
ii operator + (const ii &a,const ii &b){
    if (a.Y != b.Y) {
        __int128 xx = (__int128)a.X*b.Y, yy = (__int128)a.Y*b.X, zz = (__int128)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 {
        __int128 xx = __int128(a.X + b.X), yy = __int128(a.Y);
        __int128 gcd = __gcd(xx,yy);
        xx /= gcd, yy /= gcd;
        ii ret = ii(xx,yy);
        return ret;
    }
}
ii divi(ii a,ii b){
    __int128 xx = (__int128)a.X * b.Y, yy = (__int128)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), c = ii(sum/n,1), 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) {
        int bst = -1;
        REP (i,n) {
            if (ok[i]) continue;
            if (bst == -1 || cut[i][j] < cut[bst][j]) bst = i;
        }
        ok[bst] = true;
        ans.eb(cut[bst][j]);
        ansp[j] = bst;
    }
    REP (i,n) pary(cut[i],cut[i]+n-1);
    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 / 5
• Subtask 2: 24 / 24
• Subtask 3: 0 / 71