oj.uz

답안 #962965

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
962965 2024-04-14T10:16:19 Z n3rm1n 로봇 (IOI13_robots) C++17
14 / 100
 161 ms 21788 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
    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.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 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

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 134 ms 12888 KB Output is correct
5 Incorrect 125 ms 12884 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 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 1 ms 4552 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct
11 Incorrect 5 ms 12636 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# 결과 실행 시간 메모리 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 4548 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 3 ms 4444 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct
11 Incorrect 8 ms 12636 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12732 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 4544 KB Output is correct
7 Correct 1 ms 4696 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 161 ms 21788 KB Output is correct
11 Incorrect 147 ms 21196 KB Output isn't correct
12 Halted 0 ms 0 KB -