oj.uz

Submission #518588

# Submission time Handle Problem Language Result Execution time Memory
518588 2022-01-24T08:22:14 Z blue Sails (IOI07_sails) C++17
25 / 100
 156 ms 2628 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int rt = 3;

using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;

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

    int N;
    cin >> N;

    pii P[N];
    for(int i = 0; i < N; i++) cin >> P[i].first >> P[i].second;

    sort(P, P+N);


    vvi freq(rt, vi(rt, 0));
    vi tot(rt, 0);

    vi st(rt, 0);

    int mxh = 0;


    for(auto& p: P)
    {
        cerr << "\n\n\n\n";
        int H = p.first;
        int K = p.second;
        cerr << "sail = " << H << ' ' << K << '\n';

        while(mxh < H)
        {
            mxh++;
            cerr << "inc height\n";
            freq[0][st[0] + 0]++;
            tot[0]++;
        }

        cerr << "00 = " << freq[0][st[0]+0] << '\n';

        int ins = 0;

        for(int b = 0; b < rt; b++)
        {
            cerr << "\n\n";
            cerr << "b = " << b << " : " << rt*b << " - " << rt*b + rt-1 << '\n';
            cerr << tot[b] << " <> " << K << '\n';

            cerr << "ins = " << ins << '\n';

            // cerr << freq[b][0] << ' ' << freq[b][1] << '\n';
            if(tot[b] <= K)
            {
                cerr << "case 1\n";
                cerr << b << " : " << tot[b] << '\n';
                cerr << "K = " << K << '\n';




                cerr << "old block " << b << " : \n";
                for(int w = 0; w < rt; w++) cerr << rt*b+w << " - " << freq[b][(st[b] + w) % rt] << '\n';

                if(b == 0) cerr << "! " << rt*(b+1)+0 << " - " << freq[b+1][st[b+1]] << '\n';







                K -= tot[b];
                int new_ins = freq[b][ (st[b] + (rt-1)) % rt ];

                cerr << "ni = " << new_ins << '\n';

                st[b] = (st[b] - 1 + rt) % rt;

                tot[b] += ins - freq[b][ st[b] + 0 ];

                freq[b][ st[b] + 0 ] = ins;

                ins = new_ins;

                // K -= tot[b];

                // cerr << "new K = " << K << '\n';

                cerr << "new block " << b << " : \n";
                for(int w = 0; w < rt; w++) cerr << rt*b+w << " - " << freq[b][(st[b] + w) % rt] << '\n';
            }
            else
            {
                cerr << "case 2\n";
                cerr << K << '\n';
                int z;
                int lstv;
                for(z = 0; z < rt; z++)
                {
                    lstv = min(K, freq[b][(st[b] + z) % rt]);
                    K -= lstv;
                    if(K <= 0) break;
                }

                // cerr << "z = " << z << '\n';
                // cerr << freq[b][st[b]+z] << '\n';
                // cerr << ins << ' ' << lstv << '\n';

                if(lstv > 0 && z == rt-1)
                {
                    // cerr << "next block\n";
                    freq[b+1][st[b+1] + 0] += lstv;
                    tot[b+1] += lstv;

                    freq[b][(st[b] + z) % rt] -= lstv;
                    tot[b] -= lstv;
                }
                else
                {
                    // cerr << "curr block\n";
                    // cerr << freq[b][(st[b] + z) % rt] << ' ' << freq[b][(st[b] + z + 1) % rt] << '\n';
                    freq[b][(st[b] + z + 1) % rt] += lstv;
                    freq[b][(st[b] + z) % rt] -= lstv;
                    // cerr << " -> ";
                    // cerr << freq[b][(st[b] + z) % rt] << ' ' << freq[b][(st[b] + z + 1) % rt] << '\n';
                }

                // for(int v = 0; v < 5; v++) cerr << freq[b][st[b]+v] << ' ';
                // cerr << '\n';

                for(int y = z-1; y >= 0; y--)
                {
                    // cerr << "y = " << y << '\n';
                    freq[b][(st[b] + y + 1) % rt] += freq[b][(st[b] + y) % rt];
                    freq[b][(st[b] + y) % rt] = 0;
                    // cerr << freq[b][(st[b] + y + 1) % rt] << '\n';
                }

                freq[b][st[b]] += ins;
                tot[b] += ins;

                break;
            }
        }


        cerr << "current config = \n";
        for(ll sc = 0; sc < rt*rt; sc++)
        {
            ll occ = freq[sc/rt][(st[sc/rt] + sc%rt) % rt];

            if(occ > 0) cerr << sc << " : " << occ << '\n';

            // cerr << occ << ' ';
        }
        cerr << '\n';
        cerr << "block sizes: \n";
        for(int b = 0; b < rt; b++) cerr << b << " : " << tot[b] << '\n';
    }


    ll res = 0;
    for(ll sc = 0; sc < rt*rt; sc++)
    {
        ll occ = freq[sc/rt][(st[sc/rt] + sc%rt) % rt];

        // if(occ > 0) cerr << sc << " : " << occ << '\n';

        res += occ * ((sc-1) * sc) / 2;
    }

    cout << res << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 660 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 812 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 1228 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 156 ms 2628 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 22 ms 1768 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 38 ms 2116 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -