oj.uz

Submission #703717

# Submission time Handle Problem Language Result Execution time Memory
703717 2023-02-28T07:53:21 Z LittleCube Naan (JOI19_naan) C++14
0 / 100
 1 ms 464 KB 
#include <bits/extc++.h>
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define F first
#define S second
using namespace std;
using namespace __gnu_pbds;

const double eps = 1e-11;
int N, L, v[8][20], sum[8];
vector<int> like[8];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> N >> L;
    // why divide by N?
    // how to solve using only fractions?
    // is it guarnteed to always have a solution?
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= L; j++)
        {
            like[i].emplace_back(j);
            cin >> v[i][j];
            // sum >= sum of v / N
            // sum * N >= sum of v
            sum[i] += v[i][j];
        }
        sort(like[i].begin(), like[i].end(), [&](int x, int y)
             { return v[i][x] > v[i][y]; });
    }
    vector<int> p;
    for (int i = 1; i <= N; i++)
        p.emplace_back(i);
    do
    {
        double last = 0;
        vector<double> sol;
        for (auto i : p)
        {
            double tmp = (double)sum[i] / N;
            while (last <= L && tmp >= (ceil(last + eps) - last) * v[i][(int)ceil(last + eps)] + eps)
                tmp -= (ceil(last + eps) - last) * v[i][(int)ceil(last + eps)], last = ceil(last + eps);
            if (last > L + eps)
                goto ono;
            last += tmp / v[i][(int)ceil(last + eps)];
            sol.emplace_back(last);
        }
        sol.pop_back();
        for (auto d : sol)
        {
            for (ll nom = 1; nom <= 1'000'000; nom++)
            {
                ll c = floor(nom * d + eps);
                if(abs(double(c) / double(nom) - d) < eps)
                {
                    cout << c << ' ' << nom << '\n';
                    break;
                }
            }
        }
        for (auto i : p)
            cout << i << ' ';
        cout << '\n';
        return 0;
    ono:
        continue;
    } while (next_permutation(p.begin(), p.end()));
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 1 ms 464 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 1 ms 464 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -