Submission #703939

#	Time	Username	Problem	Language	Result	Execution time	Memory
703939		victor_gao	Naan (JOI19_naan)	C++17	29 / 100	1661 ms	68376 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;
bool vis[2015];
pii total[2015];
pii v[2015][2015],last[2015];
vector<pii>cut[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++){
        total[i]={0LL,n};
        for (int j=1;j<=l;j++){
            cin>>v[i][j].x;
            v[i][j].y=1;
            total[i].x+=v[i][j].x;
        }
        int g=__gcd(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<pii>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);
    }
    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