Submission #1170153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170153		Roupiq	Naan (JOI19_naan)	C++20	24 / 100	6 ms	584 KiB

naan

#include <bits/stdc++.h>
using namespace std;

using pii = pair<long, long>;
#define all(x) x.begin(), x.end()
#define len(x) (long)(x).size()
#define x first
#define y second

template <typename T>
ostream &operator<<(ostream &o, const vector<T> &t);
template <typename T, typename T2>
ostream &operator<<(ostream &o, const pair<T, T2> &t);

template <typename T, typename T2>
ostream &operator<<(ostream &o, const pair<T, T2> &t)
{
    return o << "{" << t.x << "," << t.y << "}";
}

template <typename T>
ostream &operator<<(ostream &o, const vector<T> &t)
{
    o << "[";
    for (long i = 0; i < len(t); i++)
    {
        o << (i ? "," : "") << t[i];
    }
    return o << "]";
}

long nxt()
{
    long x;
    cin >> x;
    return x;
}

struct Q
{
    long a, b; // a/b
    Q(long _a, long _b = 1)
    {
        a = _a, b = _b;
        long g = gcd(a, b);
        a /= g;
        b /= g;
    }
};

ostream &operator<<(ostream &o, const Q &t)
{
    return o << t.a << "/" << t.b;
}

Q operator+(Q x, Q y)
{
    return Q(x.a * y.b + y.a * x.b, x.b * y.b);
}
Q operator-(Q x, Q y)
{
    return Q(x.a * y.b - y.a * x.b, x.b * y.b);
}
Q operator*(Q x, Q y)
{
    return Q(x.a * y.a, x.b * y.b);
}
Q operator/(Q x, Q y)
{
    return Q(x.a * y.b, x.b * y.a);
}
bool operator<(Q x, Q y)
{
    return x.a * y.b < y.a * x.b;
}
bool operator==(Q x, Q y)
{
    return x.a * y.b == y.a * x.b;
}
bool operator<=(Q x, Q y)
{
    return x.a * y.b <= y.a * x.b;
}

long n, l;
vector<vector<Q>> value;

bool check(vector<long> perm)
{
    Q fpos(0);
    long pos = 0;
    vector<Q> granice;
    for (long i = 0; i < n; i++)
    {
        long o = perm[i];
        Q saturation(0);
        
        while(saturation < Q(1, n))
        {
            if(pos >= l)
                return 0;
            Q d = (Q(1, n) - saturation) / value[o][pos];
            // cout << fpos << " " << d << "\n";
            // cout << fpos + d << " < " << Q(1) << " " << (fpos + d < Q(1)) << "\n";
            if(fpos + d < Q(1))
            {
                fpos = fpos + d;
                // cout << pos << "+" << fpos << " ";
                break;
            }
            else
            {
                // cout << Q(1) - fpos << " eating -> ";
                // cout << (Q(1) - fpos) * value[o][pos] << " \n";
                saturation = saturation + (Q(1) - fpos) * value[o][pos];
                fpos = Q(0);
                pos++;
            }
            // cout << pos << "+" << fpos << " ";
        }
        granice.push_back(Q(pos) + fpos);
        // cout << " end\n";
        // break;
    }
    granice.pop_back();
    for(auto g : granice)
    {
        cout << g.a << " " << g.b << "\n";
    }
    // cout << granice << "\n";
    // cout << perm << "\n";
    for(auto p : perm)
    {
        cout << p + 1 << " ";
    }
    cout << '\n';
    return (Q(pos) + fpos) <= Q(l);
}

int main()
{
    // ios::sync_with_stdio(0), cin.tie(0);
    n = nxt(), l = nxt();
    value.resize(n);
    for (long i = 0; i < n; i++)
    {
        vector<long> koszt;
        long sumakosztow = 0;
        for (long j = 0; j < l; j++)
        {
            koszt.push_back(nxt());
            sumakosztow += koszt.back();
        }
        for (long j = 0; j < l; j++)
        {
            value[i].push_back({koszt[j], sumakosztow});
        }
        // value[i].push_back({1, 1});
    }
    // cout << value << "\n";

    vector<long> perm(n);
    iota(all(perm), 0);

    double found = false;
    do
    {
        // cout << perm << "\n";
        if (check(perm))
        {
            found = true;
            break;
        }
    } while (next_permutation(all(perm)));
    if (not found)
    {
        cout << "-1\n";
    }
}

/*
2 5
2 7 1 8 2
3 1 4 1 5

3 3
2 3 1
1 1 1
2 2 1


5 3
2 3 1
1 1 1
2 2 1
1 2 2
1 2 1
*/

• Subtask 1: 0 / 5
• Subtask 2: 24 / 24
• Subtask 3: 0 / 71