oj.uz

Submission #962973

# Submission time Handle Problem Language Result Execution time Memory
962973 2024-04-14T10:22:22 Z n3rm1n Robots (IOI13_robots) C++17
14 / 100
 125 ms 12912 KB 
#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
    
    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(x, x+a);
        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;
                }
                else if(maxx == taken[i] && putted[j] < putted[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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Incorrect 123 ms 12912 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct
11 Incorrect 6 ms 12636 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4548 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 2 ms 12632 KB Output is correct
11 Incorrect 9 ms 12756 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Incorrect 125 ms 12896 KB Output isn't correct
11 Halted 0 ms 0 KB -