oj.uz

Submission #535006

# Submission time Handle Problem Language Result Execution time Memory
535006 2022-03-09T09:18:00 Z radal Naan (JOI19_naan) C++17
24 / 100
 2 ms 352 KB 
#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
constexpr ll N = 2e3+20,mod = 1e9+7,inf = 1e18+10,maxm = 1e6;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k >>= 1;
    }
    return z;
}
int n,l;
ll a[N][N];
pll nxt[N][N];
bool mark[N];
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> l;
    rep(i,0,n){ 
        ll sum = 0;
        rep(j,0,l){
            cin >> a[i][j];
            sum += a[i][j];
            a[i][j] *= n;
        }
        ll cur = 0;
        int k = 0;
        rep(j,1,n+1){
            while (k < l && cur+a[i][k] <= sum*j){
                cur += a[i][k];
                k++;
            }
            if (k == l) nxt[i][j] = {l,1};
            else{
                ll g;
                nxt[i][j] = {(sum*j-cur)+k*a[i][k],a[i][k]};
                g = gcd(nxt[i][j].X,nxt[i][j].Y);
                nxt[i][j].X /= g;
                nxt[i][j].Y /= g;
            }
        }
    }
	auto cmp = [&] (pll x, pll y){return x.X * (y.Y/n) < (x.Y/n) * y.X;};
    vector<int> ans;
    vector<pll> out;
    rep(g,1,n+1){
        pll mi = {inf,1};
        int j = 0;
        rep(i,0,n){
            if (mark[i]) continue;
            if (cmp(mi,nxt[i][g]) == 0){
                mi = nxt[i][g];
                j = i;
            }
        }
        ans.pb(j+1);
        out.pb(mi);
        mark[j] = 1;
    }
    out.pop_back();
    for (pll p : out){
        ll g = gcd(p.X,p.Y);
        cout << p.X/g << ' ' << p.Y/g << endl;
    }
    for (int u : ans) cout << u << ' ';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Integer parameter [name=A_i] equals to 1000000000000000000, violates the range [1, 2000000000000]
4 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

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

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Integer parameter [name=A_i] equals to 1000000000000000000, violates the range [1, 2000000000000]
4 Halted 0 ms 0 KB -