Submission #962168

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
962168	2024-04-13T08:17:28 Z	sleepntsheep	Schools (IZhO13_school)	C++17	0 / 100	173 ms	17576 KB

school

#include <cstdlib>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
#include <climits>
using namespace std;

using ll = long long;
using db = long double;
using str = string; // yay python!
using vi = vector<int>;

#define A(x) begin(x), end(x)
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
#define N 200005

template <typename T>
struct rempq
{
    priority_queue<T> p, q;
    int sz=0;
    void push(T a)
    {
        p.push(a);
        ++sz;
    }

    void rem(T a)
    {
        q.push(a);
        --sz;
    }

    void pop()
    {
        while (p.size() && q.size() && q.top() == p.top())
        {
            q.pop();
            p.pop();
        }
        --sz;
        p.pop();
    }
    T top()
    {
        while (p.size() && q.size() && q.top() == p.top())
        {
            q.pop();
            p.pop();
        }
        return p.top();
    }

    int size()
    {
        return sz;
    }
};

int main()
{
    ShinLena;
    int n, k1, k2;
    cin >> n >> k1 >> k2;
    vi a(n), b(n);
    for(auto c:{&a,&b})
        for (auto &x: *c)cin>>x;


    long long mcmf = 0;

    rempq<pair<int, int>> aa, bb, ra, rb;
    for (int i=0;i<n;++i)
        aa.push({a[i], i}), bb.push({b[i], i});


    while (k1 + k2)
    {
        int op=-1;
        int flow = 0;

        if (k1&&aa.size()) op=1, flow = aa.top().first;
        if (k2&&bb.size() && bb.top().first > flow) op=2, flow=bb.top().first;
        if (k1&&ra.size() && bb.size() && ra.top().first + bb.top().first  > flow) op=3, flow=bb.top().first+ra.top().first;
        if (k2&&rb.size() && aa.size () && rb.top().first + aa.top().first>flow)op=4, flow=aa.top().first+rb.top().first;

        mcmf += flow;
        if (op==1)
        {
            int i=aa.top().second;
            aa.pop();
            bb.rem({b[i], i});
            rb.push({-a[i]+b[i], i});
            --k1;
        }
        else if(op==2)
        {
            int i=bb.top().second;
            bb.pop();
            aa.rem({a[i], i});
            ra.push({-b[i]+a[i], i});
            --k2;
        }
        else if(op==3)
        {
            int i=bb.top().second, j=ra.top().second;
            ra.pop();
            bb.pop();
            aa.rem({a[i], i});
            ra.push({-b[i]+a[i], i});
            rb.push({-a[j]+b[j], j});
            --k1;
        }
        else if(op==4)
        {
            int i=aa.top().second, j=rb.top().second;
            rb.pop();
            aa.pop();
            bb.rem({b[i], i});
            rb.push({-a[i]+b[i], i});
            ra.push({-b[j]+a[j], j});
            --k2;
        }
    }

    cout << mcmf;
    cout<<'\n';
    while(rb.size())
    {
        auto x=rb.top();
        rb.pop();
        cout<<x.second+1<<' ';
    }
    cout<<'\n';
    while(ra.size())
    {
        auto x=ra.top();
        ra.pop();
        cout<<x.second+1<<' ';
    }
    cout<<'\n';


    return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	344 KB	Output isn't correct
2	Incorrect	1 ms	344 KB	Output isn't correct
3	Incorrect	0 ms	348 KB	Output isn't correct
4	Incorrect	1 ms	348 KB	Output isn't correct
5	Incorrect	0 ms	348 KB	Output isn't correct
6	Incorrect	1 ms	348 KB	Output isn't correct
7	Incorrect	2 ms	604 KB	Output isn't correct
8	Incorrect	3 ms	600 KB	Output isn't correct
9	Incorrect	3 ms	724 KB	Output isn't correct
10	Incorrect	3 ms	604 KB	Output isn't correct
11	Incorrect	4 ms	552 KB	Output isn't correct
12	Incorrect	3 ms	604 KB	Output isn't correct
13	Incorrect	25 ms	2516 KB	Output isn't correct
14	Incorrect	26 ms	4040 KB	Output isn't correct
15	Incorrect	30 ms	6600 KB	Output isn't correct
16	Incorrect	149 ms	12444 KB	Output isn't correct
17	Incorrect	173 ms	13524 KB	Output isn't correct
18	Incorrect	131 ms	14232 KB	Output isn't correct
19	Incorrect	151 ms	15088 KB	Output isn't correct
20	Incorrect	166 ms	17576 KB	Output isn't correct