oj.uz

Submission #370431

# Submission time Handle Problem Language Result Execution time Memory
370431 2021-02-24T02:48:12 Z CodePlatina Naan (JOI19_naan) C++14
29 / 100
 393 ms 74752 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <tuple>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define piii pair<int, pii>
#define plll pair<long long, pll>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define tlll tuple<long long, long long, long long>
#define tllll tuple<long long, long long, long long, long long>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
#define DEBUG
using namespace std;
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k; cin >> n >> k;
    int A[n][k];
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < k; ++j)
            cin >> A[i][j];

    vector<plll> ls[n - 1];
    for(int i = 0; i < n; ++i)
    {
        long long s = 0;
        for(int j = 0; j < k; ++j) s += A[i][j];

        int pt = 0;
        long long pf = 0;
        for(int j = 0; j < n - 1; ++j)
        {
            while(pt < k && (pf + A[i][pt]) * n <= s * (j + 1)) pf += A[i][pt++];
            ls[j].push_back({i, { s * (j + 1) - pf * n + 1ll * pt * A[i][pt] * n, A[i][pt] * n }});
        }
    }

    for(int i = 0; i < n - 1; ++i) sort(ls[i].begin(), ls[i].end(), [](plll x, plll y){ return x.ee * y.rr < x.rr * y.ee; });

    bool chc[n]{};
    int P[n];
    pll ans[n];
    for(int i = 0; i < n - 1; ++i)
    {
        for(int j = 0; j < n; ++j) if(!chc[ls[i][j].ff])
        {
            chc[ls[i][j].ff] = true;
            P[i] = (int)ls[i][j].ff;
            ans[i] = ls[i][j].ss;
            break;
        }
    }
    for(int i = 0; i < n; ++i) if(!chc[i]) P[n - 1] = i;

    for(int i = 0; i < n - 1; ++i) cout << ans[i].ff << ' ' << ans[i].ss << '\n';
    for(int i = 0; i < n; ++i) cout << P[i] + 1 << ' ';
}

Subtask #1
5.0 / 5.0

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

Subtask #2
24.0 / 24.0

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

Subtask #3
0 / 71.0

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