Submission #1245957

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245957		jer033	Parking (CEOI22_parking)	C++20	20 / 100	79 ms	6592 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

vector<pii> answer;
queue<int> free_spaces;
vector<pii> cars;//what are the cars in this parking space?
vector<pii> locs;//where are my cars?
priority_queue<pii> handle_next;

int classify_car(int c, int loc)
{
    if ((cars[loc].first == c) and (cars[loc].second != c))
        return 2;//top
    if ((cars[loc].first == 0) and (cars[loc].second == c))
        return 3;//only
    if ((cars[loc].first != 0) and (cars[loc].second == c))
        return 1;//bottom
    return 0;//either it does not exist, or both cars are same color -> done
}

int classify_pair(int c)
{
    int x = classify_car(c, locs[c].first);
    int y = classify_car(c, locs[c].second);
    if (x < y)
    {
        swap(x, y);
        swap(locs[c].first, locs[c].second);
    }
    if ((x == 1) and (y == 1))
        return 1;
    if ((x == 2) and (y == 1))
        return 2;
    if ((x == 2) and (y == 2))
        return 4;
    if ((x == 3) and (y == 1))
        return 3;
    if ((x == 3) and (y == 2))
        return 5;
    if ((x == 3) and (y == 3))
        return 6;
    return 0;
}

bool possible = 1;

int find_free()
{
    //ONLY CALL WHEN NECESSARY!!!
    if (free_spaces.empty())
    {
        possible = 0;
        return -1;
    }
    int x = free_spaces.front();
    if (cars[x].second == 0)
        return x;
    free_spaces.pop();
    return find_free();
}

int coun;

void handle(int c)
{
    int k = classify_pair(c);
    int xx = locs[c].first;
    int yy = locs[c].second;
    if (k==6)
    {
        //adds a free space
        answer.push_back({yy, xx});
        free_spaces.push(yy);
        cars[yy] = {0, 0};
        cars[xx] = {c, c};
        locs[c] = {xx, xx};
        coun++;
    }
    else if (k==5)
    {
        //no effect
        answer.push_back({yy, xx});
        cars[yy].first = 0;
        cars[xx] = {c, c};
        locs[c] = {xx, xx};
        int kk = classify_pair(cars[yy].second);
        handle_next.push({kk, cars[yy].second});
        coun++;
    }
    else if (k==4)
    {
        //min answer += 1
        //free spaces -= 1, but we "upgrade" some of the others
        int t = find_free();
        if (t!=-1)
        {
            int g = cars[yy].second;
            int h = cars[xx].second;
            answer.push_back({yy, t});
            answer.push_back({xx, t});
            cars[t] = {c, c};
            cars[xx] = {0, h};
            cars[yy] = {0, g};
            locs[c] = {t, t};
            
            int kk = classify_pair(g);
            handle_next.push({kk, g});
            int kkk = classify_pair(h);
            handle_next.push({kkk, h});
            coun++;
        }
    }
    else if (k==3)
    {
        //answer += 1
        //requires a free space, but does not consume it
        int t = find_free();
        if (t!=-1)
        {
            int g = cars[yy].first;
            answer.push_back({yy, t});
            answer.push_back({yy, xx});
            cars[yy] = {0, 0};
            cars[t] = {0, g};
            cars[xx] = {c, c};
            free_spaces.push(yy);
            locs[c] = {xx, xx};
            if (locs[g].first == yy)
                locs[g].first = t;
            if (locs[g].second == yy)
                locs[g].second = t;
            int kk = classify_pair(g);
            handle_next.push({kk, g});
            coun++;
        }
    }
    else if (k==2)
    {
        //answer += 1
        //consumes a free space
        int t = find_free();
        if (t!=-1)
        {
            int g = cars[yy].first;
            int h = cars[xx].second;
            answer.push_back({yy, t});
            answer.push_back({xx, yy});
            cars[yy] = {c, c};
            cars[xx] = {0, h};
            cars[t] = {0, g};
            locs[c] = {yy, yy};

            if (locs[g].first == yy)
                locs[g].first = t;
            if (locs[g].second == yy)
                locs[g].second = t;
            
            int kk = classify_pair(g);
            handle_next.push({kk, g});
            int kkk = classify_pair(h);
            handle_next.push({kkk, h});
            coun++;
        }
    }
    else
    {
        possible = 0;
    }
}

int main()
{
    possible = 1;
    int n, m; cin >> n >> m;
    cars = vector<pii> (m+1, {0, 0});
    locs = vector<pii> (n+1, {0, 0});
    coun = 0;
    for (int i=1; i<=m; i++)
    {
        cin >> cars[i].second >> cars[i].first;
        if (cars[i].second == 0)
            free_spaces.push(i);
        
        if (locs[cars[i].first].first == 0)
            locs[cars[i].first].first = i;
        else
            locs[cars[i].first].second = i;

        if (locs[cars[i].second].first == 0)
            locs[cars[i].second].first = i;
        else
            locs[cars[i].second].second = i;

        if ((cars[i].first == cars[i].second) and (cars[i].first > 0))
            coun++;
    }

    for (int i=1; i<=n; i++)
    {
        int k = classify_pair(i);
        handle_next.push({k, i});
    }

    while ((coun < n) and (possible == 1))
    {
        pii t = handle_next.top(); handle_next.pop();
        int k = t.first; int c = t.second;
        if (k == classify_pair(c))
            handle(c);
    }

    if (coun == n)
    {
        int q = answer.size();
        cout << q << '\n';
        for (int i=0; i<q; i++)
            cout << answer[i].first << ' ' << answer[i].second << '\n';
    }
    else
    {
        cout << "-1\n";
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 15
• Subtask 5: 0 / 25
• Subtask 6: 0 / 15