Submission #969317

#	Time	Username	Problem	Language	Result	Execution time	Memory
969317		ThegeekKnight16	Robots (IOI13_robots)	C++17	0 / 100	6 ms	8796 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
vector<int> pai, sub, minId;

void buildDsu(int ySize)
{
    pai.resize(ySize+1); sub.resize(ySize+1); minId.resize(ySize+1);
    iota(pai.begin(), pai.end(), 0);
    fill(sub.begin(), sub.end(), 1);
    iota(minId.begin(), minId.end(), 0);
}
int find(int v) {return pai[v] = (pai[v] == v ? v : find(pai[v]));}
void une(int a, int b)
{
    a = find(a), b = find(b);
    if (a == b) return;
    if (sub[a] < sub[b]) swap(a, b);
    pai[b] = a;
    sub[a] += sub[b];
    minId[a] = min(minId[a], minId[b]);
}

bool Test(int x, int A, int B, int T, int *X, int *Y, const vector<pair<int, int>> &Toy, int ySize)
{
    if ((long long)x*(A+B) < T) return 0;
    int idT = T-1, idA = A-1;
    vector<int> remain(ySize+1); buildDsu(ySize);
    for (int i = 0; i < B; i++) une(Y[i], Y[i]-1);
    while (idT >= 0 && idA >= 0)
    {
        // cerr << "idA: " << idA << ", idT: " << idT << '\n';
        if (X[idA] > Toy[idT].first)
        {
            int canDelete = x;
            int id = find(ySize);
            while (canDelete > 0 && minId[id] > 0)
            {
                int mD = minId[id];
                une(mD, mD-1);
                id = find(id);
                --canDelete;
            }
            --idA;
        }
        else if (minId[find(Toy[idT].second)] == Toy[idT].second)
        {
            remain[Toy[idT].second] = 1;
            une(Toy[idT].second, Toy[idT].second-1);
            --idT;
        }
        else idT--;
    }
    while (idT >= 0)
    {
        if (minId[find(Toy[idT].second)] == Toy[idT].second)
        {
            remain[Toy[idT].second] = 1;
            une(Toy[idT].second, Toy[idT].second-1);
        }
        --idT;
    }
    while (idA >= 0)
    {
        int canDelete = x;
        int id = find(ySize);
        while (canDelete > 0 && minId[id] > 0)
        {
            int mD = minId[id];
            une(mD, mD-1);
            id = find(id);
            --canDelete;
        }
        --idA;
    }
    // cerr << "PENIS" << '\n';
    auto idR = 1; int idB = 0;
    int cnt = 0;
    while (idR < remain.size() && idB < B)
    {
        if (Y[idB] <= idR) cnt = max(0, cnt-x), idB++;
        else cnt += remain[idR++];
    }
    if (idR < remain.size()) cnt += remain[idR++];
    while (idB < B) cnt = max(0, cnt-x), idB++;

    return (cnt == 0);
}

int putaway(int A, int B, int T, int X[], int Y[], int _W[], int _S[])
{
    vector<pair<int, int>> yVals;
    for (int i = 0; i < T; i++) yVals.emplace_back(_S[i], -(i+1));
    for (int i = 0; i < B; i++) yVals.emplace_back(Y[i], i+1);
    sort(yVals.begin(), yVals.end());

    for (int i = 0; i < yVals.size(); i++)
    {
        auto [val, id] = yVals[i];
        if (id < 0) _S[id-1] = i+1;
        else Y[id-1] = i+1;
    }

    vector<pair<int, int>> Toy(T);
    for (int i = 0; i < T; i++) Toy[i] = make_pair(_W[i], _S[i]);
    sort(X, X+A); sort(Y, Y+B);
    for (int i = 0; i < T; i++) if (Toy[i].first >= X[A-1] && Toy[i].second >= Y[B-1]) return -1;
    sort(Toy.begin(), Toy.end());

    int ini = 1, fim = T;
    while (ini < fim)
    {
        int m = (ini + fim) >> 1;
        if (Test(m, A, B, T, X, Y, Toy, yVals.size())) fim = m;
        else ini = m+1;
    }
    return fim;
}

Compilation message (stderr)

robots.cpp: In function 'bool Test(int, int, int, int, int*, int*, const std::vector<std::pair<int, int> >&, int)':
robots.cpp:79:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     while (idR < remain.size() && idB < B)
      |            ~~~~^~~~~~~~~~~~~~~
robots.cpp:84:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     if (idR < remain.size()) cnt += remain[idR++];
      |         ~~~~^~~~~~~~~~~~~~~
robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:97:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for (int i = 0; i < yVals.size(); i++)
      |                     ~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 25
• Subtask 4: 0 / 37
• Subtask 5: 0 / 10