oj.uz

답안 #962168

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
962168 2024-04-13T08:17:28 Z sleepntsheep 학교 설립 (IZhO13_school) C++17
0 / 100
 173 ms 17576 KB 
#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

# 결과 실행 시간 메모리 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