Submission #702649

#	Time	Username	Problem	Language	Result	Execution time	Memory
702649		victor_gao	Naan (JOI19_naan)	C++17	29 / 100	4 ms	724 KiB

naan

//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int n,l,total[10];
pii v[10][2015],last[2015];
pii add(pii a,pii b){
    int up=(a.x*b.y+a.y*b.x);
    int down=(a.y*b.y);
    if (up==0||down==0)
         return {up,down};
    int g=__gcd(up,down);
    return {up/g,down/g};
}
pii sub(pii a,pii b){
    int up=(a.x*b.y-a.y*b.x);
    int down=(a.y*b.y);
    if (up==0||down==0)
         return {up,down};
    int g=__gcd(up,down);
    return {up/g,down/g};
}
pii mul(pii a,pii b){
    int up=a.x*b.x;
    int down=a.y*b.y;
    if (up==0||down==0)
         return {up,down};
    int g=__gcd(up,down);
    return {up/g,down/g};
}
bool bigger(pii a,pii b){
    return a.x*b.y>=a.y*b.x;
}
signed main(){
    fast
    cin>>n>>l;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=l;j++){
            cin>>v[i][j].x;
            total[i]+=v[i][j].x;
            v[i][j].y=1;
            last[j]={1,1};
        }
    }
    vector<int>all;
    for (int i=1;i<=n;i++)
        all.push_back(i);
    bool flag=0;
    do {
        pii ans[10];
        vector<pii>cut;
        for (int i=1;i<=n;i++)
            ans[i]={0,1};
        for (int i=1;i<=l;i++)
            last[i]={1,1};
        int p=0;
        pii now={0,1};
        for (int i=1;i<=l;i++){
            if (p>=n) break;
            int j=all[p];
            while (last[i]!=make_pair(0LL,0LL)){
                if (bigger(mul(add(ans[j],mul(v[j][i],last[i])),{n,1}),{total[j],1})){
                    pii need=sub({total[j],n},ans[j]);
                    pii use=mul(need,{v[j][i].y,v[j][i].x});
                 //   cout<<j<<" -> "<<need.x<<" "<<need.y<<' '<<use.x<<" "<<use.y<<'\n';
                    last[i]=sub(last[i],use);
                    now=add(now,use);
                    cut.push_back(now);
                    ans[j]=add(ans[j],mul(v[j][i],use));
                    p++;
                    if (p>=n) break;
                    j=all[p];
                 //   cout<<j<<" -> "<<last[i].x<<" "<<last[i].y<<'\n';
                }
                else {
                    ans[j]=add(ans[j],mul(v[j][i],last[i]));
                    now=add(now,last[i]);
                    last[i]={0,0};
                }
            }
        }
        if (p>=n){
            cut.pop_back();
            for (auto i:cut)
                cout<<i.x<<' '<<i.y<<'\n';
            for (auto i:all)
                cout<<i<<" ";
            cout<<'\n';
            flag=1;
            break;
        }
    }while (next_permutation(all.begin(),all.end()));
    if (!flag) cout<<-1<<'\n';
}

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