oj.uz

Submission #992017

# Submission time Handle Problem Language Result Execution time Memory
992017 2024-06-03T14:42:47 Z browntoad Naan (JOI19_naan) C++14
29 / 100
 1 ms 604 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define FOR(i,a,b) for (int i = (a); i<(b); i++)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)
#define RREP(i,n) for (int i=(n)-1; i>=0; i--)
#define RREP1(i,n) for (int i=(n); i>=1; i--)
#define f first
#define s second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)(x.size())
#define SQ(x) (x)*(x)
#define pii pair<int, int>
#define pip pair<int, pii>
#define ppi pair<pii, int>
#define pdd pair<double ,double>
#define pcc pair<char, char>
#define endl '\n'
//#define TOAD
#ifdef TOAD
#define bug(x) cerr<<__LINE__<<": "<<#x<<" is "<<x<<endl
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#endif
 
const double PI=acos(-1);
const ll maxn = 4e5+5;
const ll maxm = 3e3+5;
const ll inf = 1ll<<60;
const ll mod = 998244353;
 
ll pw(ll a, ll p){
    ll ret = 1;
    while(p > 0){
        if (p&1){
            ret *= a;
            ret %= mod;
        }
        a *= a;
        a %= mod;
        p >>= 1;
    }
    return ret;
}
ll inv(ll a){
    return pw(a, mod-2);
}
 
int n, L;
struct frac{
    int num, dem;
};
frac operator +(frac &a, frac &b){
    return {a.num*b.dem + a.dem*b.num, a.dem*b.dem};
}
frac operator -(frac &a, frac &b){
    return {a.num*b.dem - a.dem*b.num, a.dem*b.dem};
}
frac operator *(frac &a, frac &b){
    return {a.num*b.num, a.dem*b.dem};
}
bool operator <(frac &a, frac &b){
  	assert(a.num <= 1e18 && b.num <= 1e18 && a.dem <= 1e18 && b.dem <= 1e18);
    return (__int128)a.num*b.dem < (__int128)a.dem*b.num;
}
 
signed main(){
    IOS();
    cin>>n>>L;
    vector<vector<frac>> vc(n);
    vector<vector<int>> in(n);
    vector<vector<frac>> pls(n);
    REP(i, n){
        vc[i].resize(L);
        in[i].resize(L);
        pls[i].resize(n);
 
        int tot = 0;
        REP(j, L) {
            cin>>vc[i][j].num;
            in[i][j] = vc[i][j].num;
            tot += vc[i][j].num;
            vc[i][j].dem = 1;
        }
 
        int tt = 0;
        REP(j, n){
            frac gl = {tot, n};
            while(vc[i][tt] < gl){
                gl = (gl-vc[i][tt]);
                vc[i][tt] = {0, 1};
                tt++;
            }
            //cout<<gl.num<<"///"<<gl.dem<<endl;
            //cout<<vc[i][tt].num<<"///"<<vc[i][tt].dem<<' '<<tt<<endl;
 
            frac tmp = {tt+1, 1};
            vc[i][tt] = (vc[i][tt] - gl);
            frac tmp2 = {vc[i][tt].num, vc[i][tt].dem*in[i][tt]};
            pls[i][j] = (tmp - tmp2);
            //cout<<pls[i][j].num<<'/'<<pls[i][j].dem<<' ';
            if (vc[i][tt].num == 0){ // 0
                //cout<<tt<<endl;
                tt++;
            }
        }
    }
 
    vector<int> perm;
    vector<bool> occ(n);
    REP(i, n){
        pair<frac, int> mn = {{L+1, 1}, -1};
        REP(j, n){
            if (!occ[j] && pls[j][i] < mn.f) {
                mn.f = pls[j][i];
                mn.s = j;
            }
        }
 
        if (i != n-1) cout<<mn.f.num<<' '<<mn.f.dem<<endl;
        perm.pb(mn.s+1);
        occ[mn.s] = 1;
 
    }
    REP(i, n) cout<<perm[i]<<' ';
    cout<<endl;
 
 
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 376 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 408 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 0 ms 604 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 0 ms 604 KB Output is correct
16 Correct 1 ms 600 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 0 ms 604 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 1 ms 604 KB Output is correct

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 376 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 408 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 0 ms 604 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 604 KB Output is correct
30 Correct 0 ms 604 KB Output is correct
31 Correct 1 ms 600 KB Output is correct
32 Correct 1 ms 604 KB Output is correct
33 Correct 1 ms 604 KB Output is correct
34 Correct 1 ms 604 KB Output is correct
35 Correct 1 ms 604 KB Output is correct
36 Correct 1 ms 604 KB Output is correct
37 Correct 1 ms 604 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 1 ms 604 KB Output is correct
40 Correct 0 ms 604 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 1 ms 604 KB Output is correct
43 Runtime error 1 ms 600 KB Execution killed with signal 6
44 Halted 0 ms 0 KB -