Submission #553898

#	Time	Username	Problem	Language	Result	Execution time	Memory
553898		elazarkoren	Robots (IOI13_robots)	C++17	39 / 100	123 ms	19596 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const int MAX_T = 50 + 5;
const int MAX_A = 50 + 5;
const int MAX_B = 50 + 5;

int a, b, t;
int x[MAX_A], y[MAX_B], w[MAX_T], s[MAX_T];

int matched[MAX_T * (MAX_A + MAX_B)];

bool FindMatch(vvi &graph, int node, bitset<MAX_T> &visited) {
    visited[node] = true;
    for (int neighbor : graph[node]) {
        if (matched[neighbor] == -1 || !visited[matched[neighbor]] && FindMatch(graph, matched[neighbor], visited)) {
            matched[neighbor] = node;
            return true;
        }
    }
    return false;
}

bool Match(vvi &graph, int sz) {
    fill(matched, matched + sz, -1);
    for (int i = 0; i < t; i++) {
        bitset<MAX_T> visited;
        if (!FindMatch(graph, i, visited)) {
            return false;
        }
    }
    return true;
}

vii robots;

bool Ok(int time) {
    vvi graph(t);
    for (int i = 0; i < t; i++) {
        for (int j = 0; j < a + b; j++) {
            if (robots[j].y && s[i] < y[robots[j].x] || !robots[j].y && w[i] < x[robots[j].x]) {
                for (int k = 0; k < time; k++) {
                    graph[i].push_back(j + (a + b) * k);
                }
            }
        }
    }
    return Match(graph, (a + b) * time);
//    int ind = 0;
//    for (int i = 0; i < a && ind < t; i++) {
//        int j = min(ind + time, t);
//        for (; ind < j && w[ind] < x[i]; ind++);
//    }
//    return ind == t;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    a = A, b = B, t = T;
    for (int i = 0; i < a; i++) x[i] = X[i];
    for (int i = 0; i < b; i++) y[i] = Y[i];
    for (int i = 0; i < t; i++) w[i] = W[i], s[i] = S[i];
    for (int i = 0; i < a; i++) {
        robots.push_back({i, 0});
    }
    for (int j = 0; j < b; j++) {
        robots.push_back({j, 1});
    }
    int begin = 0, end = t + 1, mid;
    while (begin < end) {
        mid = (begin + end) >> 1;
        if (Ok(mid)) {
            end = mid;
        } else begin = mid + 1;
    }
    if (end == t + 1) return -1;
    return end;
//    for (int i = 0; i < t; i++) {
//        int count = 0;
//        for (int j = 0; j < 2; j++) {
//            if (robots[j].y && s[i] < y[robots[j].x]) {
//                good[i][j] = true;
//                count++;
//            } else if (!robots[j].y && w[i] < x[robots[j].x]) {
//                good[i][j] = true;
//                count++;
//            }
//        }
//        if (!count) return -1;
//    }
//    if (good[0][0] && good[1][1] || good[1][0] && good[0][1]) return 1;
//    return 2;
}
/*
3 0 6
6 2 9
4 6
8 5
7 9
1 8
5 1
8 7
*/

Compilation message (stderr)

robots.cpp: In function 'bool FindMatch(vvi&, int, std::bitset<55>&)':
robots.cpp:27:68: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   27 |         if (matched[neighbor] == -1 || !visited[matched[neighbor]] && FindMatch(graph, matched[neighbor], visited)) {
      |                                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
robots.cpp: In function 'bool Ok(int)':
robots.cpp:52:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   52 |             if (robots[j].y && s[i] < y[robots[j].x] || !robots[j].y && w[i] < x[robots[j].x]) {

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