oj.uz

Submission #703939

# Submission time Handle Problem Language Result Execution time Memory
703939 2023-03-01T04:17:07 Z victor_gao Naan (JOI19_naan) C++17
29 / 100
 1661 ms 68376 KB 
//#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 388 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 388 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 1 ms 436 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 524 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 388 KB Output is correct
13 Correct 1 ms 520 KB Output is correct
14 Correct 2 ms 620 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 2 ms 596 KB Output is correct
19 Correct 2 ms 596 KB Output is correct
20 Correct 2 ms 596 KB Output is correct
21 Correct 2 ms 528 KB Output is correct
22 Correct 2 ms 524 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 2 ms 596 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 2 ms 596 KB Output is correct

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 388 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 388 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 1 ms 436 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 524 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 2 ms 596 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 2 ms 596 KB Output is correct
25 Correct 2 ms 596 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 1 ms 388 KB Output is correct
28 Correct 1 ms 520 KB Output is correct
29 Correct 2 ms 620 KB Output is correct
30 Correct 2 ms 596 KB Output is correct
31 Correct 2 ms 596 KB Output is correct
32 Correct 2 ms 596 KB Output is correct
33 Correct 2 ms 596 KB Output is correct
34 Correct 2 ms 596 KB Output is correct
35 Correct 2 ms 596 KB Output is correct
36 Correct 2 ms 528 KB Output is correct
37 Correct 2 ms 524 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Correct 2 ms 596 KB Output is correct
40 Correct 1 ms 468 KB Output is correct
41 Correct 1 ms 468 KB Output is correct
42 Correct 2 ms 596 KB Output is correct
43 Correct 243 ms 14712 KB Output is correct
44 Incorrect 1661 ms 68376 KB X_i is not increasing
45 Halted 0 ms 0 KB -