Submission #375292

#	Time	Username	Problem	Language	Result	Execution time	Memory
375292		jass921026	Naan (JOI19_naan)	C++14	0 / 100	1 ms	492 KiB

naan

#include<bits/stdc++.h>
using namespace std;
#define jizz ios_base::sync_with_stdio(false);cin.tie(NULL);
#define mp make_pair
#define int long long
typedef pair<int,int> pii;
#define F first
#define S second
int v[7][7], sum[7], p[7];
pii f[7];
int gcd(int a, int b){
    return !b?a:gcd(b,a%b);
}
pii add(pii a, pii b){
    pii c={a.F*b.S+a.S*b.F,a.S*b.S};
    int g=gcd(c.F,c.S);
    c.F/=g;
    c.S/=g;
    return c;
}
pii sub(pii a, pii b){
    pii c={a.F*b.S-a.S*b.F,a.S*b.S};
    int g=gcd(c.F,c.S);
    c.F/=g;
    c.S/=g;
    return c;
}
pii mul(pii a, pii b){
    pii c={a.F*b.F,a.S*b.S};
    int g=gcd(c.F,c.S);
    c.F/=g;
    c.S/=g;
    return c;
}
int to_int(pii a){
    return a.F/a.S;
}
bool operator<(pii a, pii b){//1 for < , 0 for >
    return a.F*b.S<=a.S*b.F;
}
signed main(){
    int n, L;
    cin>>n>>L;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=L;j++){
            cin>>v[i][j];
            sum[i]+=v[i][j];
        }
    }
    for(int i=1;i<=n;i++) p[i]=i;
    bool ok;
    do{
        pii x={0,1};
        for(int i=1;i<=n;i++) f[i]={0,1};
        for(int i=1;i<=n;i++){
            //cout<<"x= "<<x.F<<" "<<x.S<<"\n";
            pii cur=mp(0,1);
            int nxt=to_int(x)+1;
            if(mp(sum[p[i]],n)<mul(mp(v[p[i]][nxt],1),mp(nxt*x.S-x.F,x.S))){
                if(i==n) ok=1;
                f[i]=add(mul(mp(sum[p[i]],n),mp(1,v[p[i]][nxt])),x);
                x=f[i];
                continue;
            } else{
                cur=mul(mp(v[p[i]][nxt],1),mp(nxt*x.S-x.F,x.S));
                x=mp(nxt,1);
            }
            //cout<<"cur= "<<cur.F<<" "<<cur.S<<"\n";
            while(x.F<=L){
                if(mp(sum[p[i]],n)<add(cur,mp(v[p[i]][x.F+1],1))){
                    if(i==n) ok=1;
                    f[i]=add(x,mul(sub(mp(sum[p[i]],n),cur),mp(1,v[p[i]][x.F+1])));
                    x=f[i];
                    break;
                } else{
                    cur=add(cur,mp(v[p[i]][x.F+1],1));
                    //cout<<cur.F<<" "<<cur.S<<"\n";
                    x.F++;
                    //cout<<x.F<<"\n";
                }
            }
        }
    } while(!ok&&next_permutation(p+1,p+n+1));
    if(ok){
        for(int i=1;i<n;i++){
            cout<<f[i].F<<" "<<f[i].S<<"\n";
        }
        for(int i=1;i<=n;i++){
            cout<<p[i]<<" \n"[i==n];
        }
    } else{
        cout<<"-1\n";
    }
    return 0;
}
/*
2 5
2 7 1 8 2
3 1 4 1 5
*/
/*
7 1
1 2 3 4 5 6 7
*/
/*
5 3
2 3 1
1 1 1
2 2 1
1 2 2
1 2 1
*/

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