oj.uz

Submission #1057698

# Submission time Handle Problem Language Result Execution time Memory
1057698 2024-08-14T03:41:19 Z hotboy2703 Naan (JOI19_naan) C++17
29 / 100
 105 ms 70228 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);
                cur = sum;
            }
            assert(cur==sum);
            cut[i][j] = MP(A,B);
            // assert(B<=1e9);
            // if (j>1)assert(cut[i][j].fi * cut[i][j-1].se > cut[i][j-1].fi * cut[i][j].se);
            // 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-1;j ++){
        cout<<sus[j].fi<<' '<<sus[j].se<<'\n';
    }
    for (ll j = 1;j <= n;j ++)cout<<p[j]<<' ';
}

Subtask #1
5.0 / 5.0

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

Subtask #2
24.0 / 24.0

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

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2392 KB Output is correct
17 Correct 1 ms 4440 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct
22 Correct 0 ms 2396 KB Output is correct
23 Correct 1 ms 4444 KB Output is correct
24 Correct 1 ms 4444 KB Output is correct
25 Correct 1 ms 4444 KB Output is correct
26 Correct 1 ms 4444 KB Output is correct
27 Correct 1 ms 4444 KB Output is correct
28 Correct 1 ms 4444 KB Output is correct
29 Correct 1 ms 4444 KB Output is correct
30 Correct 1 ms 4444 KB Output is correct
31 Correct 1 ms 4444 KB Output is correct
32 Correct 1 ms 4444 KB Output is correct
33 Correct 1 ms 4444 KB Output is correct
34 Correct 1 ms 4444 KB Output is correct
35 Correct 1 ms 4512 KB Output is correct
36 Correct 1 ms 4444 KB Output is correct
37 Correct 1 ms 4444 KB Output is correct
38 Correct 1 ms 2396 KB Output is correct
39 Correct 1 ms 4580 KB Output is correct
40 Correct 1 ms 4444 KB Output is correct
41 Correct 1 ms 2396 KB Output is correct
42 Correct 1 ms 4444 KB Output is correct
43 Correct 18 ms 31068 KB Output is correct
44 Incorrect 105 ms 70228 KB X_i is not increasing
45 Halted 0 ms 0 KB -