제출 #703945

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
703945		victor_gao	Naan (JOI19_naan)	C++17	29 / 100	279 ms	23180 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 ll __int128
#define pii pair<ll,ll>
#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;
bool vis[2015];
pii total[2015];
pii v[2015][2015],last[2015];
vector<pii>cut[2015];
pii add(pii a,pii b){
    ll up=(a.x*b.y+a.y*b.x);
    ll down=(a.y*b.y);
    if (up==0||down==0)
         return {up,down};
    ll g=__gcd(up,down);
    return {up/g,down/g};
}
pii sub(pii a,pii b){
    ll up=(a.x*b.y-a.y*b.x);
    ll down=(a.y*b.y);
    if (up==0||down==0)
         return {up,down};
    ll g=__gcd(up,down);
    return {up/g,down/g};
}
pii mul(pii a,pii b){
    ll up=a.x*b.x;
    ll down=a.y*b.y;
    if (up==0||down==0)
         return {up,down};
    ll g=__gcd(up,down);
    return {up/g,down/g};
}
bool bigger(pii a,pii b){
    return (__int128)a.x*b.y>=(__int128)a.y*b.x;
}
signed main(){
    fast
    cin>>n>>l;
    for (int i=1;i<=n;i++){
        total[i]={0LL,n};
        for (int j=1;j<=l;j++){
            int val; cin>>val;
            v[i][j].x=val;
            v[i][j].y=1;
            total[i].x+=v[i][j].x;
        }
        ll g=__gcd((ll)n,total[i].x);
        total[i]={total[i].x/g,total[i].y/g};
    }
 //   cout<<"OK\n";
    for (int i=1;i<=n;i++){
        for (int j=1;j<=l;j++)
            last[j]={1,1};
        pii now={0,1},val={0,1};
        int p=1;
        for (int j=1;j<=n;j++){
            val={0,1};
            while (val!=total[i]){
             //   cout<<p<<" : "<<val.x<<","<<val.y<<" "<<total[i].x<<','<<total[i].y<<'\n';
                if (bigger(add(val,mul(v[i][p],last[p])),total[i])){
                    pii need=sub(total[i],val);
                    pii use=mul(need,{1,v[i][p].x});
                    last[p]=sub(last[p],use);
                    now=add(now,use);
                    val=add(val,mul(v[i][p],use));
                    cut[i].push_back(now);
               ///     cout<<i<<" add "<<now.x<<" "<<now.y<<'\n';
                }
                else {
                    val=add(val,mul(v[i][p],last[p]));
                    now=add(now,last[p]);
                    last[p]={0LL,1LL};
                    p++;
                }
            }
        }
    }
    vector<int>order;
    vector<pair<int,int> >pos;
    for (int i=0;i<n;i++){
        pii small={2*l,1};
        int use=0;
        for (int j=1;j<=n;j++){
            if (!vis[j]&&bigger(small,cut[j][i])){
                use=j;
                small=cut[j][i];
            }
        }
        vis[use]=1;
        order.push_back(use);
        pos.push_back({small.x,small.y});
    }
    pos.pop_back();
    for (auto i:pos)
        cout<<i.x<<" "<<i.y<<'\n';
    for (auto i:order)
        cout<<i<<" ";
    cout<<'\n';
}

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