Submission #1349279

#	Time	Username	Problem	Language	Result	Execution time	Memory
1349279		feyza	Robots (IOI13_robots)	C++20	Compilation error	0 ms	0 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"

using namespace std;

const int maxn=1e6+5;
const int maxa=5e4+5;
int w[maxn],s[maxn];
int x[maxa],y[maxa];

int sz[maxn],weight[maxn];
bool used[maxn];

bool cmpsz(int a,int b)
{
    if(s[a]!=s[b])
        return s[a]<s[b];
    return w[a]<w[b];
}

bool cmpw(int a,int b)
{
    if(w[a]!=w[b])
        return w[a]<w[b];
    return s[a]<s[b];
}

int bin_search_w(int src,int & T)
{
    int l=0,r=T-1,mid;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(w[weight[mid]]<src)
            l=mid+1;
        else
            r=mid-1;
    }

    return l-1;
}

int bin_search_s(int src,int & T)
{
    int l=0,r=T-1,mid;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(s[sz[mid]]<src)
            l=mid+1;
        else
            r=mid-1;
    }

    return l-1;
}

bool check(int curr,int & A,int & B,int & T)
{
    //cout<<"curr "<<curr<<endl;

    for(int i=0;i<T;i++)
        used[i]=false;

    int idx=0,cnt;
    set<pair<int,int>,greater<pair<int,int>>>st;
    for(int i=0;i<A;i++)
    {
        while(idx<T && w[weight[idx]]<x[i])
        {
            if(!used[weight[idx]])
            {
                st.insert({s[weight[idx]],weight[idx]});
            }
            idx++;
        }

        cnt=0;
        while(!st.empty() && cnt<curr)
        {
            pair<int,int> ch=*(st.begin());
            used[ch.second]=true;
            st.erase(st.begin());
            cnt++;
        }
    }


    idx=0;
    st.clear();
    for(int i=0;i<B;i++)
    {
        while(idx<T && s[sz[idx]]<y[i])
        {
            if(!used[sz[idx]])
            {
                st.insert({w[sz[idx]],sz[idx]});
            }
            idx++;
        }

        cnt=0;
        while(!st.empty() && cnt<curr)
        {
            pair<int,int> ch=*(st.begin());
            used[ch.second]=true;
            st.erase(st.begin());
            cnt++;
        }
    }

    for(int i=0;i<T;i++)
    {
        if(!used[i])
            return false;
    }

    return true;
}

int putaway(int A, int B, int T,int X[], int Y[], int W[], int S[])
{
    for(int i=0;i<A;i++)
        x[i]=X[i];
    for(int i=0;i<B;i++)
        y[i]=Y[i];

    for(int i=0;i<T;i++)
    {
        sz[i]=i;
        weight[i]=i;
        w[i]=W[i]; s[i]=S[i];
    }

    sort(sz,sz+T,cmpsz);
    sort(weight,weight+T,cmpw);
    sort(x,x+A);
    sort(y,y+B);

    int l=1,r=T,mid;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(check(mid,A,B,T))
            r=mid-1;
        else
            l=mid+1;
    }

    if(l>T)
        return -1;

    return l;
}

int a1,b1,t1,x11[maxa],y11[maxa],w1[maxn],s1[maxn];

int main()
{
    cin>>a1;
    for(int i=0;i<a1;i++)
        cin>>x11[i];
    cin>>b1;
    for(int i=0;i<b1;i++)
        cin>>y11[i];
    cin>>t1;
    for(int i=0;i<t1;i++)
        cin>>w1[i]>>s1[i];

    cout<<putaway(a1,b1,t1,x11,y11,w1,s1)<<endl;

    return 0;
}

/**
2
2 5
1
2
3
3 1
5 3
2 2

3
6 2 9
2
4 7
10
4 6
8 5
2 3
7 9
1 8
5 1
3 3
8 7
7 6
10 5
**/

Compilation message (stderr)

/usr/bin/ld: /tmp/ccNpG7dp.o: in function `main':
grader.c:(.text.startup+0x0): multiple definition of `main'; /tmp/ccFO4GZO.o:robots.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status