oj.uz

Submission #191337

# Submission time Handle Problem Language Result Execution time Memory
191337 2020-01-14T17:15:15 Z dolphingarlic Naan (JOI19_naan) C++14
0 / 100
 141 ms 127592 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (ll i = x; i < y; i++)
typedef long long ll;
using namespace std;

ll gcd(ll A, ll B) { return (B ? gcd(B, A % B) : A); }

struct Rational {
    ll x, y; // x/y

    Rational(ll num = 1, ll den = 1) {
        ll g = gcd(num, den);
        x = num / g;
        y = den / g;
    }

    Rational operator+(Rational B) { return Rational(x * B.y + B.x * y, y * B.y); }
    Rational operator-(Rational B) { return Rational(x * B.y - B.x * y, y * B.y); }
    Rational operator*(Rational B) { return Rational(x * B.x, y * B.y); }
};

bool operator<(Rational A, Rational B) { return A.x * B.y < A.y * B.x; }
ostream& operator<<(ostream& os, const Rational& A) {
    os << A.x << ' ' << A.y;
    return os;
}

Rational cut_places[2001][2001];
bool visited[2001];
ll order[2001], a[2001];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n, l;
    cin >> n >> l;
    FOR(i, 0, n) {
        ll sm = 0;
        FOR(j, 0, l) {
            cin >> a[j];
            sm += a[j];
        }

        Rational curr = Rational(0), target = Rational(sm, n);
        int idx = 0;
        FOR(j, 0, l) {
            while (target < curr + Rational(a[j])) {
                Rational offset = target - curr;
                cut_places[i][idx++] = Rational(j) + offset * Rational(1, a[j]);
                target = target + Rational(sm, n);

                // Error here
                assert(Rational(0) < cut_places[i][idx - 1]);
                assert(Rational(0) < offset);
                assert(Rational(0) < target);
            }
            curr = curr + Rational(a[j]);
        }
    }

    FOR(i, 0, n - 1) {
        Rational earliest = Rational(1000000000);
        FOR(j, 0, n) if (!visited[j] & cut_places[j][i] < earliest) {
            earliest = cut_places[j][i], j;
            order[i] = j;
        }
        cout << earliest << '\n';
        visited[order[i]] = true;
    }
    FOR(i, 0, n) if (!visited[i]) order[n - 1] = i;
    FOR(i, 0, n) cout << order[i] + 1 << ' ';
    return 0;
}

Compilation message

naan.cpp: In function 'int main()':
naan.cpp:63:57: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
         FOR(j, 0, n) if (!visited[j] & cut_places[j][i] < earliest) {
                                        ~~~~~~~~~~~~~~~~~^~~~~~~~~~
naan.cpp:64:43: warning: right operand of comma operator has no effect [-Wunused-value]
             earliest = cut_places[j][i], j;
                                           ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 141 ms 127580 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 138 ms 127592 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Runtime error 141 ms 127580 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -