Submission #109162

#	Time	Username	Problem	Language	Result	Execution time	Memory
109162		dantoh000	로봇 (IOI13_robots)	C++14	76 / 100	3101 ms	28476 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
int w[1000005], s[1000005];
bool cmpw(int a, int b){
    if (w[a] != w[b]) return w[a] < w[b];
    else return s[a] < s[b];
}
bool cmps(int a, int b){
    if (s[a] != s[b]) return s[a] < s[b];
    else return w[a] < w[b];
}
bool cando(int x, int A, int B, int T, int X[], int Y[], int W[], int S[]){
    //printf("\t\t\t\tTesting %d\n",x);
    vector<int> v(T);
    for (int i = 0; i < T; i++) v[i] = i;
    sort(v.begin(),v.end(),cmpw);
    int curT = 0, curA = 0;
    priority_queue<ii> pq;
    while (curT < T && curA < A){
        //printf("toy %d weight %d robot %d\n",v[curT],W[v[curT]],curA);
        if (X[curA] <= W[v[curT]]){
            int num = 0;
            while (num++ < x && pq.size()){
                //printf("robot %d takes %d weight %d\n",curA,pq.top().second,pq.top().first);
                pq.pop();
            }
            curA++;
        }
        else{
            pq.push(ii(S[v[curT]],v[curT]));
            curT++;
        }
    }
    while (curA++ < A){
        int num = 0;
        while (num++ < x && pq.size()){
            //printf("robot %d takes %d size %d\n",curA,pq.top().second,pq.top().first);
            pq.pop();
        }
    }
    vector<int> v2;
    while(pq.size()){
        v2.push_back(pq.top().second);
        //printf("toy %d not taken by weight\n",pq.top().second);
        pq.pop();
    }
    while (curT < T){
        //printf("toy %d not taken by weight\n",v[curT]);
        v2.push_back(v[curT++]);
    }
    sort(v2.begin(),v2.end(),cmps);
    int curB = 0;
    curT = 0;
    while (curT < v2.size() && curB < B){
        //printf("toy %d size %d robot %d\n",v2[curT],S[v2[curT]],curB);
        if (Y[curB] <= S[v2[curT]]){
            int num = 0;
            while (num++ < x && pq.size()){
                //printf("robot %d takes %d size %d\n",curB,pq.top().second,pq.top().first);
                pq.pop();
            }
            curB++;
        }
        else{
            pq.push(ii(W[v2[curT]],v2[curT]));
            curT++;
        }
    }
    while (curB++ < B){
        int num = 0;
        while (num++ < x && pq.size()){
            //printf("robot %d takes %d size %d\n",curB,pq.top().second,pq.top().first);
            pq.pop();
        }
    }
    if (pq.empty() && curT == v2.size()){
        //printf("none left\n");
        return true;
    }
    else{
        //printf("some left\n");
        while (pq.size()){
            //printf("toy %d not taken\n",pq.top().second);
            pq.pop();
        }
        return false;
    }
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    for (int i = 0; i < T; i++){
        w[i] = W[i];
        s[i] = S[i];
    }
    sort(X,X+A);
    sort(Y,Y+B);
	int lo = 0, hi = T+1;
	while (lo + 1 < hi){
        //printf("%d %d\n",lo,hi);
        int mid = (lo+hi)/2;
        if (cando(mid,A,B,T,X,Y,W,S)){
            hi = mid;
        }
        else lo = mid;
	}
	if (lo + 1 == hi){
        //printf("%d %d\n",lo,hi);
        if (cando(lo,A,B,T,X,Y,W,S)) hi = lo;
        else lo = hi;
	}
	if (lo == T+1) return -1;
	return lo;
}

Compilation message (stderr)

robots.cpp: In function 'bool cando(int, int, int, int, int*, int*, int*, int*)':
robots.cpp:56:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (curT < v2.size() && curB < B){
            ~~~~~^~~~~~~~~~~
robots.cpp:78:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (pq.empty() && curT == v2.size()){
                       ~~~~~^~~~~~~~~~~~

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