Submission #139430

#	Time	Username	Problem	Language	Result	Execution time	Memory
139430		MrBrionix	Robots (IOI13_robots)	C++14	100 / 100	1921 ms	22968 KiB

robots

#include <stdio.h>
#include <stdlib.h>
#include "robots.h"
#include<bits/stdc++.h>
using namespace std;


int low,up,mid,wei[100000],siz[100000],cont,cont2;
pair<int,int> v[1000005];
priority_queue<int> pq;


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

    for(int i=0;i<A;i++)wei[i]=X[i];
    for(int i=0;i<B;i++)siz[i]=Y[i];
    
    for(int i=0;i<T;i++)v[i]={W[i],S[i]};
    
    sort(v,v+T);
    sort(wei,wei+A);
    sort(siz,siz+B);
    
    while(up-low>1){
     
        mid=(up+low)/2;
        while(pq.size()>0)pq.pop();   
        cont=0;
        
        for(int i=0;i<A;i++){
            
            while(cont<T && v[cont].first<wei[i]){
                pq.push(v[cont].second);
                cont++;
            }
            
            cont2=0;
            
            while(cont2<mid && pq.size()>0){
                pq.pop();
                cont2++;   
            }
        }
        
        while(cont<T){
            pq.push(v[cont].second);
            cont++;
        }
        
        for(int j=B-1;j>=0;j--){
            cont2=0;
            while(cont2<mid && pq.size()>0 && pq.top()<siz[j]){
                pq.pop();
                cont2++;
            }
        }
        
        if(pq.size()>0)low=mid;
        else up=mid;
    }


    if(up==T+1)return -1;
    return up;
}
/*
#define fail(s, x...) do { \
		fprintf(stderr, s "\n", ## x); \
		exit(1); \
	} while(0)

#define MAX_A 50000
#define MAX_B 50000
#define MAX_T 500000

static int X[MAX_A];
static int Y[MAX_B];
static int W[MAX_T];
static int S[MAX_T];

int main() {
    int A, B, T, i;
	int res;

	FILE *f = fopen("input.txt", "r");
	if (!f)
		fail("Failed to open input file.");

	res = fscanf(f, "%d", &A);
	if (res != 1)
		fail("Failed to read A from input file.");
	if (A < 0 || A > MAX_A)
		fail("A is out of bounds.");

	res = fscanf(f, "%d", &B);
	if (res != 1)
		fail("Failed to read B from input file.");
	if (B < 0 || B > MAX_B)
		fail("B is out of bounds.");

	res = fscanf(f, "%d", &T);
	if (res != 1)
		fail("Failed to read T from input file.");
	if (T < 1 || T > MAX_T)
		fail("T is out of bounds.");

	for (i = 0; i < A; i++) {
		res = fscanf(f, "%d", &X[i]);
		if (res != 1)
		    fail("Failed to read data from input file.");
    }
	for (i = 0; i < B; i++) {
        res = fscanf(f, "%d", &Y[i]);
        if (res != 1)
            fail("Failed to read data from input file.");
    }
	for (i = 0; i < T; i++) {
        res = fscanf(f, "%d%d", &W[i], &S[i]);
        if (res != 2)
            fail("Failed to read data from input file.");
    }
	fclose(f);

	int answer = putaway(A, B, T, X, Y, W, S);

	printf("%d\n", answer);

	return 0;
}*/

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