oj.uz

답안 #974968

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
974968 2024-05-04T08:13:33 Z n3rm1n 로봇 (IOI13_robots) C++17
0 / 100
 4 ms 22876 KB 
#include<bits/stdc++.h>
#include"robots.h"
using namespace std;
const int MAXN = 1e6 + 10;
int a, b, tcnt, x[MAXN], y[MAXN], s[MAXN], w[MAXN];

int xt;
int fr[MAXN * 4], t[MAXN * 4];

struct toys
{
    int w, s, id;
    toys(){};
    toys(int _w, int _s, int _id)
    {
        w = _w;
        s = _s;
        id = _id;
    }
};
vector < toys > g;
bool cmp(toys t1, toys t2)
{
    if(t1.s != t2.s)return (t1.s > t2.s);
    if(t1.w != t2.w)return (t1.w > t2.w);
    return (t1.id < t2.id);
}
void make_tree(int i, int l, int r)
{
    if(l > r)return;
    if(l == r)
    {
        fr[l] = xt;
        t[i] = x[l];
        return;
    }
    int mid = (l + r)/2;
    make_tree(2*i, l, mid);
    make_tree(2*i+1, mid+1, r);
    t[i] = max(t[2*i], t[2*i+1]);
    //cout << l << " " << r << " " << t[i] << endl;
}
int wei, no = 0;
int query(int i, int l, int r)
{
    if(l > r)
    {
        no = 1;
        return 0;
    }
    if(l == r)
    {
        if(t[i] <= wei)no = 1;
        return l;
    }
    int mid = (l + r)/2;
    if(t[2*i] > wei)return query(2*i, l, mid);
    else return query(2*i+1, mid+1, r);
}
int indexx;
void update(int i, int l, int r)
{
    if(l > r)return;
    if(l == r)
    {
        fr[l] --;
        if(fr[l] == 0)t[i] = -1;
        else t[i] = x[l];
        return;
    }
    int mid = (l + r)/2;
    if(indexx <= mid)update(2*i, l, mid);
    else update(2*i+1, mid+1, r);
    t[i] = max(t[2*i], t[2*i+1]);
}
int marked[MAXN];
int usedy[MAXN];
bool check(int curr_xt)
{
    memset(marked, 0, sizeof(marked));
    xt = curr_xt;
   // cout << endl;
   // cout << xt << " is the time " << endl;
   // cout << endl;
    make_tree(1, 0, a-1);
    for (int i = 0; i < g.size(); ++ i)
    {
        int weight = g[i].w;
        no = 0;
        wei = weight;
        indexx = query(1, 0, a-1);
        //cout << weight << ", " << g[i].id << " is on " << indexx << endl;
        //cout << " but no = " << no << endl;
        if(no == 1)continue;
        update(1, 0, a-1);
        marked[g[i].id] = 1;
    }
    vector < int > u;
    for (int i = 0; i < tcnt; ++ i)
    {
        if(!marked[i])u.push_back(s[i]);
    }
    sort(u.begin(), u.end());
   /* for (int i = 0; i < u.size(); ++ i)
        cout << u[i] << " ";
    cout << endl;*/
    memset(usedy, 0, sizeof(usedy));
    int curr = 0;
    for (int i = 0; i < u.size(); ++ i)
    {
        while(curr < b && y[curr] <= u[i] || usedy[curr] == xt)curr ++;
        if(curr < b)
        {
            usedy[curr] ++;
        }
        else return false;
    }
    return true;
}



int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
    sort(X, X+A);
    sort(Y, Y+B);

    for (int i = 0; i < T; ++ i)
    {
        s[i] = S[i];
        w[i] = W[i];
        g.push_back(toys(w[i], s[i], i));
    }

    sort(g.begin(), g.end(), cmp);

    /*for (int i = 0; i < g.size(); ++ i)
        cout << g[i].w << " ";
    cout << endl;
    for (int i = 0; i < g.size(); ++ i)
        cout << g[i].s << " ";
    cout << endl;
    for (int i = 0; i < g.size(); ++ i)
        cout << g[i].id << " ";
    cout << endl;*/
    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;
    tcnt = T;

    int l = 0, r = tcnt, mid, ans = tcnt;
    while(l <= r)
    { mid = (l + r)/2;
        if(check(mid))
        {
            ans = mid;
            r = mid -1;
        }
        else l = mid + 1;
    }
    return ans;
}

Compilation message

robots.cpp: In function 'bool check(int)':
robots.cpp:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<toys>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for (int i = 0; i < g.size(); ++ i)
      |                     ~~^~~~~~~~~~
robots.cpp:109:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for (int i = 0; i < u.size(); ++ i)
      |                     ~~^~~~~~~~~~
robots.cpp:111:24: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  111 |         while(curr < b && y[curr] <= u[i] || usedy[curr] == xt)curr ++;

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 22872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 20956 KB Output is correct
2 Incorrect 4 ms 20828 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 22872 KB Output is correct
2 Incorrect 3 ms 22876 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 22876 KB Output is correct
2 Incorrect 4 ms 22876 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 22876 KB Output is correct
2 Incorrect 3 ms 22876 KB Output isn't correct
3 Halted 0 ms 0 KB -