oj.uz

Submission #702649

# Submission time Handle Problem Language Result Execution time Memory
702649 2023-02-24T17:00:13 Z victor_gao Naan (JOI19_naan) C++17
29 / 100
 4 ms 724 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,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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 400 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 448 KB Output is correct
12 Correct 1 ms 352 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 2 ms 348 KB Output is correct
15 Correct 1 ms 340 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 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 4 ms 456 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 472 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 2 ms 468 KB Output is correct
21 Correct 1 ms 584 KB Output is correct
22 Correct 2 ms 468 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Correct 1 ms 444 KB Output is correct
25 Correct 1 ms 480 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 468 KB Output is correct

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 400 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 448 KB Output is correct
12 Correct 1 ms 352 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 2 ms 348 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 2 ms 468 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 4 ms 456 KB Output is correct
25 Correct 2 ms 596 KB Output is correct
26 Correct 2 ms 468 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 2 ms 472 KB Output is correct
31 Correct 2 ms 468 KB Output is correct
32 Correct 2 ms 468 KB Output is correct
33 Correct 2 ms 468 KB Output is correct
34 Correct 1 ms 468 KB Output is correct
35 Correct 2 ms 468 KB Output is correct
36 Correct 1 ms 584 KB Output is correct
37 Correct 2 ms 468 KB Output is correct
38 Correct 0 ms 340 KB Output is correct
39 Correct 1 ms 444 KB Output is correct
40 Correct 1 ms 480 KB Output is correct
41 Correct 1 ms 340 KB Output is correct
42 Correct 1 ms 468 KB Output is correct
43 Runtime error 2 ms 724 KB Execution killed with signal 11
44 Halted 0 ms 0 KB -