Submission #873091

#	Time	Username	Problem	Language	Result	Execution time	Memory
873091		ofrankel	Naan (JOI19_naan)	C++17	29 / 100	19 ms	4184 KiB

naan

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,l;
vector<vector<int>>v;
ll gc(ll a,ll b){
    if(!b)return a;
    return gc(b,a%b);
}
class frac{
public:
    ll a,b;
    frac(ll _a,ll _b):a(_a),b(_b){reduce();}
    frac(ll x):a(x),b(1){}
    void reduce(){if(int g=gc(a,b)){a/=g;b/=g;}}
    bool operator <(const frac& other){return a*other.b<other.a*b;}
    frac operator +( const frac& other){return frac(a*other.b+b*other.a,b*other.b);}
};
pair<vector<pair<int,int>>,vector<int>> solve(int N,int L,vector<vector<int>>V){
    n=N;l=L;v=move(V);
    vector<int>was(n);
    vector<int>p(n);
    vector<int>s(n);for(int i=0;n>i;++i)for(int j:v[i])s[i]+=j;
    vector<pair<int,int>>t(n-1);
    frac cur(0);
    for(int cyc=0;n>cyc+1;++cyc){
        frac nxt(l);
        int cind,c=cur.a/cur.b;
        frac cc((c+1)*cur.b-cur.a,cur.b);
        for(int i=0;n>i;++i)if(!was[i]){
            if(cc.a*n*v[i][c]>=cc.b*s[i]){
                frac tmp=frac(s[i],v[i][c]*n);
                if(tmp<nxt){nxt=tmp;cind=i;}
            }
            else{
                ll cb=cur.b;
                ll cl=s[i]*cur.b;
                ll ck=cc.a*v[i][c];
                int j=c+1;
                while(l>j&&(ck+v[i][j]*cb)*n<cl){ck+=v[i][j]*cb;++j;}
                if(j==l)continue;
                ll tt=cl-ck*n;
                frac tmp=frac(tt,n*cb*v[i][j])+cc+frac(j-c-1);
                if(tmp<nxt){nxt=tmp;cind=i;}
            }
        }
        cur=cur+nxt;
        was[cind]=1;
        p[cyc]=1+cind;
        t[cyc]={cur.a,cur.b};
    }
    for(int i=0;n>i;++i)if(!was[i])p[n-1]=i+1;
    return {t,p};
}


int main()
{
    std::ios::sync_with_stdio(0);cin.tie(0);
    int N,L;cin>>N>>L;
    vector<vector<int>>V(N,vector<int>(L));
    for(auto&i:V)for(auto&j:i)cin>>j;
    auto [t,p]=solve(N,L,move(V));
    if(t.size()==0&&p.size()==0)
        cout<<-1<<endl;
    else{
        for(auto [a,b]:t)
            cout<<a<<" "<<b<<"\n";
        for(int i:p)
            cout<<i<<" ";
        cout<<"\n";
    }
    return 0;
}

Compilation message (stderr)

naan.cpp: In function 'std::pair<std::vector<std::pair<int, int> >, std::vector<int> > solve(int, int, std::vector<std::vector<int> >)':
naan.cpp:49:17: warning: 'cind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   49 |         p[cyc]=1+cind;
      |                ~^~~~~

• Subtask 1: 5 / 5
• Subtask 2: 24 / 24
• Subtask 3: 0 / 71