Submission #962965

#	Time	Username	Problem	Language	Result	Execution time	Memory
962965		n3rm1n	Robots (IOI13_robots)	C++17	14 / 100	161 ms	21788 KiB

robots

#include<bits/stdc++.h>
#include"robots.h"
using namespace std;
const int MAXN = 1e6 + 10;
int a, b, t, x[MAXN], y[MAXN], s[MAXN], w[MAXN];
bool check(int xt)
{
    int index = 0;
    for (int i = 0; i < a; ++ i)
    {
        if(index == t)return true;
        int put = 0;
        while(index < t && put < xt && w[index] < x[i])
        {
            index ++;
            put ++;
        }
    }
    return (index == t);
}


int taken[55];
int putted[55];
int is[55][55];
int putaway(int A,int B,int T, int X[],int Y[],int W[],int S[])
{
    /// 14p
    if(A + B == 2 && T == 2)
    {
        int fit00 = 0, fit01 = 0, fit10 = 0, fit11 = 0;
        if(A == 2)
        {
            if(W[0] < X[0])fit00 ++;
            if(W[1] < X[0])fit01 ++;
            if(W[0] < X[1])fit10 ++;
            if(W[1] < X[1])fit11 ++;
        }
        else if(B == 2)
        {
            if(S[0] < Y[0])fit00 ++;
            if(S[1] < Y[0])fit01 ++;
            if(S[0] < Y[1])fit10 ++;
            if(S[1] < Y[1])fit11 ++;
        }
        else
        {
            if(W[0] < X[0])fit00 ++;
            if(W[1] < X[0])fit01 ++;
            if(S[0] < Y[0])fit10 ++;
            if(S[1] < Y[0])fit11 ++;
        }
        if(!fit01 && !fit11)return -1;
        if(!fit00 && !fit10)return -1;
        if(fit01 && fit10)return 1;
        if(fit00 && fit11)return 1;
        return 2;
    }
    /// sort + make global
    sort(X, X+A);
    sort(Y, Y+B);
    for (int i = 0; i < T; ++ i)
    {
        s[i] = S[i];
        w[i] = W[i];
    }
    for (int i = 0; i < A; ++ i)
        x[i] = X[i];
    for (int i = 0; i < B; ++ i)
        y[i] = Y[i];

    a = A;
    b = B;
    t = T;


    if(B == 0)
    {
        sort(w, w+T);
        if(X[A-1] <= W[T-1])return -1;
        int l = 1, r = t, mid = 0, ans = t;
        while(l <= r)
        {
            mid = (l + r)/2;
            if(check(mid))
            {
                ans = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        return ans;
    }


    for (int i = 0; i < a; ++ i)
    {
        for (int j = 0; j < t; ++ j)
        {
            if(w[j] < x[i])
            {
               is[i][j] = 1;
               putted[j] ++;
               taken[i] ++;
            }
        }
    }
    for (int i = 0; i < b; ++ i)
    {
        for (int j = 0; j < t; ++ j)
        {
            if(s[j] < y[i])
            {
               is[i+a][j] = 1;
               putted[j] ++;
               taken[i+a] ++;
            }
        }
    }
    int all = 0;
    for(int i = 0; i < t; ++ i)
    {
        if(!putted[i])return -1;
        all += putted[i];
    }

    while(all > t)
    {
        int maxx = 0, maxi = 0, maxj = 0;
        for (int i = 0; i < a+b; ++ i)
        {
            for (int j = 0; j < t; ++ j)
            {
                if(is[i][j] && putted[j] > 1 && maxx < taken[i])
                {
                    maxx = taken[i];
                    maxi = i;
                    maxj = j;
                }
            }
        }
        is[maxi][maxj] --;
        taken[maxi] --;
        putted[maxj] --;
        all --;
    }
    int ans = 0;
    for (int i = 0; i < a+b; ++ i)
        ans = max(ans, taken[i]);
    return ans;
}

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