oj.uz

Submission #1057628

# Submission time Handle Problem Language Result Execution time Memory
1057628 2024-08-14T02:00:35 Z hotboy2703 Naan (JOI19_naan) C++17
0 / 100
 1 ms 2396 KB 
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll MAXN = 2e3+100;
const ll INF = 1e18;
ll n,L;
ll v[MAXN][MAXN];
pll cut[MAXN][MAXN];
bool in[MAXN];
ll p[MAXN];
pll sus[MAXN];
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);
    cin>>n>>L;
    for (ll i = 1;i <= n; i++){
        ll sum = 0;
        for (ll j = 1;j <= L;j ++){
            cin>>v[i][j];
            v[i][j] *= n;
            sum += v[i][j];
        }
        sum /= n;
        ll A = 0,B = 1;
        for (ll j = 1;j <= n;j ++){
            ll cur = 0;
            while (cur < sum && (B-A%B) * v[i][A/B+1] / B + cur <= sum)cur+=(B-A%B) * v[i][A/B+1] / B,A+=(B-A%B),A/=B,B=1;
            if (cur < sum){
                if (B==1){
                    B=v[i][A/B+1];
                    A *= B;
                }
                A += (sum - cur);
            }
            cut[i][j] = MP(A,B);
            // cout<<A<<' '<<B<<endl;
        }
    }
    for (ll i = 1; i<= n;i ++)in[i] = 1;
    for (ll j = 1;j <= n;j ++){
        ll best = -1;
        for (ll i = 1;i <= n;i ++){
            if (in[i] == 1){
                if (best==-1)best = i;
                else{
                    ll a1 = cut[best][j].fi,b1 = cut[best][j].se;
                    ll a2 = cut[i][j].fi,b2 = cut[i][j].se;
                    if (a1*b2>a2*b1)best = i;
                }
            }
        }
        in[best] = 0;
        p[j]=best;
        sus[j] = cut[best][j];
    }
    for (ll j = 1;j <= n;j ++){
        cout<<sus[j].fi<<' '<<sus[j].se<<'\n';
    }
    for (ll j = 1;j <= n;j ++)cout<<p[j]<<' ';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Integer parameter [name=P_i] equals to 5, violates the range [1, 2]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2396 KB Integer parameter [name=P_i] equals to 1168, violates the range [1, 2]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Integer parameter [name=P_i] equals to 5, violates the range [1, 2]
2 Halted 0 ms 0 KB -