oj.uz

답안 #974973

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
974973 2024-05-04T08:23:03 Z n3rm1n 로봇 (IOI13_robots) C++17
100 / 100
 2359 ms 48876 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;
    if(a != 0)
    {
        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;
           // cout << g[i].id << endl;
        }
    }
    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;*/
    // cout << u.size() << 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 = 1, r = tcnt, mid, ans = -1;
    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:89:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<toys>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for (int i = 0; i < g.size(); ++ i)
      |                         ~~^~~~~~~~~~
robots.cpp:115:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for (int i = 0; i < u.size(); ++ i)
      |                     ~~^~~~~~~~~~
robots.cpp:117:24: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  117 |         while(curr < b && y[curr] <= u[i] || usedy[curr] == xt)curr ++;

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 22876 KB Output is correct
2 Correct 4 ms 18780 KB Output is correct
3 Correct 3 ms 20828 KB Output is correct
4 Correct 3 ms 22876 KB Output is correct
5 Correct 2 ms 18780 KB Output is correct
6 Correct 3 ms 20828 KB Output is correct
7 Correct 3 ms 20828 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Correct 3 ms 20828 KB Output is correct
3 Correct 3 ms 20828 KB Output is correct
4 Correct 1436 ms 42552 KB Output is correct
5 Correct 996 ms 41652 KB Output is correct
6 Correct 222 ms 26828 KB Output is correct
7 Correct 2359 ms 40984 KB Output is correct
8 Correct 1938 ms 43776 KB Output is correct
9 Correct 1038 ms 43204 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 22876 KB Output is correct
2 Correct 3 ms 23008 KB Output is correct
3 Correct 3 ms 22872 KB Output is correct
4 Correct 3 ms 18780 KB Output is correct
5 Correct 3 ms 20828 KB Output is correct
6 Correct 3 ms 22876 KB Output is correct
7 Correct 3 ms 18780 KB Output is correct
8 Correct 3 ms 20828 KB Output is correct
9 Correct 3 ms 20824 KB Output is correct
10 Correct 4 ms 22872 KB Output is correct
11 Correct 4 ms 22968 KB Output is correct
12 Correct 4 ms 23128 KB Output is correct
13 Correct 4 ms 22876 KB Output is correct
14 Correct 4 ms 22876 KB Output is correct

Subtask #4
37.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 22876 KB Output is correct
2 Correct 3 ms 22876 KB Output is correct
3 Correct 3 ms 23004 KB Output is correct
4 Correct 3 ms 18780 KB Output is correct
5 Correct 3 ms 20932 KB Output is correct
6 Correct 3 ms 22876 KB Output is correct
7 Correct 3 ms 18780 KB Output is correct
8 Correct 3 ms 20824 KB Output is correct
9 Correct 3 ms 20828 KB Output is correct
10 Correct 4 ms 23012 KB Output is correct
11 Correct 4 ms 22876 KB Output is correct
12 Correct 4 ms 22876 KB Output is correct
13 Correct 4 ms 22876 KB Output is correct
14 Correct 4 ms 22876 KB Output is correct
15 Correct 4 ms 22876 KB Output is correct
16 Correct 23 ms 25372 KB Output is correct
17 Correct 23 ms 25484 KB Output is correct
18 Correct 16 ms 25372 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 22876 KB Output is correct
2 Correct 3 ms 22876 KB Output is correct
3 Correct 3 ms 22996 KB Output is correct
4 Correct 3 ms 19032 KB Output is correct
5 Correct 4 ms 20828 KB Output is correct
6 Correct 3 ms 22876 KB Output is correct
7 Correct 3 ms 18780 KB Output is correct
8 Correct 3 ms 20828 KB Output is correct
9 Correct 3 ms 20928 KB Output is correct
10 Correct 1426 ms 42400 KB Output is correct
11 Correct 1010 ms 41660 KB Output is correct
12 Correct 227 ms 27044 KB Output is correct
13 Correct 2327 ms 40980 KB Output is correct
14 Correct 1916 ms 43776 KB Output is correct
15 Correct 4 ms 22876 KB Output is correct
16 Correct 4 ms 22876 KB Output is correct
17 Correct 5 ms 22876 KB Output is correct
18 Correct 4 ms 22872 KB Output is correct
19 Correct 4 ms 22876 KB Output is correct
20 Correct 4 ms 22996 KB Output is correct
21 Correct 24 ms 25456 KB Output is correct
22 Correct 840 ms 41264 KB Output is correct
23 Correct 1030 ms 42964 KB Output is correct
24 Correct 1416 ms 45492 KB Output is correct
25 Correct 1960 ms 45240 KB Output is correct
26 Correct 532 ms 48876 KB Output is correct
27 Correct 2254 ms 47800 KB Output is correct
28 Correct 2242 ms 47532 KB Output is correct
29 Correct 1059 ms 47800 KB Output is correct