Submission #433321

#	Time	Username	Problem	Language	Result	Execution time	Memory
433321		lucaperju	Robots (IOI13_robots)	C++14	100 / 100	552 ms	23024 KiB

robots

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

int n,na,nb;

bool desc (int a, int b)
{
    return a>b;
}

struct ura
{
    int a,b,ok;
}v[1000003];

bool cmp (ura a, ura b)
{
    return a.b<b.b;
}
int cnta[50003],cntb[50003],nxta[50003],nxtb[50003];

int getnextA(int pz)
{
    if(nxta[pz]==pz)
        return pz;
    return nxta[pz]=getnextA(nxta[pz]);
}

void addToA (int pz, int val)
{
    int pzadd=getnextA(v[pz].a);
    if(pzadd)
    {
        v[pz].ok=1;
        ++cnta[pzadd];
        if(cnta[pzadd]==val)
            nxta[pzadd]=nxta[pzadd-1];
    }
}

int getnextB(int pz)
{
    if(nxtb[pz]==pz)
        return pz;
    return nxtb[pz]=getnextB(nxtb[pz]);
}

void addToB (int pz, int val)
{
    int pzadd=getnextB(v[pz].b);
    if(pzadd)
    {
        v[pz].ok=1;
        ++cntb[pzadd];
        if(cntb[pzadd]==val)
            nxtb[pzadd]=nxtb[pzadd-1];
    }
}

bool verif (int val)
{
    for(int i=1;i<=na;++i)
        cnta[i]=0,nxta[i]=i;
    for(int i=1;i<=nb;++i)
        cntb[i]=0,nxtb[i]=i;
    for(int i=1;i<=n;++i)
    {
        v[i].ok=0;
        addToA(i,val);
    }
    for(int i=1;i<=n;++i)
    {
        if(!v[i].ok)
            addToB(i,val);
        if(!v[i].ok)
            return false;
    }
    return true;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    n=T;
    na=A;
    nb=B;
    sort(X,X+A,desc);
    sort(Y,Y+B,desc);
    int ok=1;
    for(int i=0;i<T;++i)
    {
        int k=-1;
        int pas=(1<<15);
        while(pas)
        {
            if(k+pas<A && X[k+pas]>W[i])
                k+=pas;
            pas>>=1;
        }
        v[i+1].a=k+1;
        k=-1;
        pas=(1<<15);
        while(pas)
        {
            if(k+pas<B && Y[k+pas]>S[i])
                k+=pas;
            pas>>=1;
        }
        v[i+1].b=k+1;
        v[i+1].ok=0;
        if(v[i+1].a == 0 && v[i+1].b == 0)
            return -1;
    }
    sort(v+1,v+T+1,cmp);
    int pas=(1<<19);
    int k=0;
    while(pas)
    {
        if(!verif(k+pas))
            k+=pas;
        pas>>=1;
    }
    return k+1;
}


/*
#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("a.in", "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;
}*/

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:88:9: warning: unused variable 'ok' [-Wunused-variable]
   88 |     int ok=1;
      |         ^~

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