Submission #245218

#	Time	Username	Problem	Language	Result	Execution time	Memory
245218		cfalas	Robots (IOI13_robots)	C++14	0 / 100	44 ms	65540 KiB

robots

#include <stdio.h>
#include <stdlib.h>
#include "robots.h"
#include<algorithm>
#include<iostream>
#include<vector>

struct diplo{
int x;
int y;
int i;
};

bool ff(diplo x,diplo y){
    return x.y>y.y || x.y==y.y && x.x>y.x;
}

bool ff2(diplo x,diplo y){
    return x.x>y.x || x.x==y.x && x.y>y.y;
}


using namespace std;

int putaway(int a, int b, int n, int x[], int y[], int w[], int s[]) {

    int f[2200000]={};
    if(a!=0)
    sort(x,x+a);
    if(b!=0)
    sort(y,y+b);

    for(int i=0;i<n;i++){
            if(a==0)
            f[i]++;
    else
        if(w[i]>=x[a-1])
            f[i]++;
    }
    for(int i=0;i<n;i++){
        if(b==0)
            f[i]++;
    else
        if(s[i]>=y[b-1])
            f[i]++;
    }
    for(int i=0;i<n;i++){
       if(f[i]==2){
        f[0]=-1;
       }
       //cout<<f[i]<<" ";
    }
    if(f[0]==-1)
        return -1;

    vector < diplo > row;
    vector < vector < diplo > > vx(1200000,row);
    for(int i=0;i<a;i++){
        for(int j=0;j<n;j++){
            if(x[i]>w[j]){
                diplo t;
                t.x=w[j];
                t.y=s[j];
                t.i=j;
                vx[i].push_back(t);
            }
                }
    }

    vector < diplo > row2;
    vector < vector < diplo > > vy(1200000,row2);
    for(int i=0;i<b;i++){
        for(int j=0;j<n;j++){
            if(y[i]>s[j]){
                diplo t;
                t.x=w[j];
                t.y=s[j];
                t.i=j;
                vy[i].push_back(t);
            }
                }
    }
/*
    cout<<endl;
    for(int i=0;i<a;i++){
            cout<<x[i]<<" : ";
            sort(vx[i].begin() , vx[i].end(),ff);
        for(int j=0;j<vx[i].size();j++){
            cout<<vx[i][j].x<<" "<<vx[i][j].y<<"  ."<<vx[i][j].i<<" /   ";
        }
    cout<<endl;
    }

    cout<<endl;
    for(int i=0;i<b;i++){
            cout<<y[i]<<" : ";
            sort(vy[i].begin() , vy[i].end(),ff2);
        for(int j=0;j<vy[i].size();j++){
            cout<<vy[i][j].x<<" "<<vy[i][j].y<<"  ."<<vy[i][j].i<<" /   ";
        }
    cout<<endl;
    }
*/
    int ans=1200000;
    int l=1;
    int r=n;

    while(l<=r){

    int mid=(l+r)/2;

    int c[2020000]={};
    int k=mid;
    int c2=0;
     for(int i=0;i<a;i++){
            sort(vx[i].begin() , vx[i].end(),ff);
            int cou=0;
        for(int j=0;j<vx[i].size();j++){
            if(c[vx[i][j].i]==0){
            c[vx[i][j].i]=1;
            cou++;
            c2++;
            }
            if(cou==k)
                break;
        }
      //  for(int j=0;j<n;j++){
       //     cout<<c[j]<<" ";
      //  }
    //cout<<endl;
    }


    for(int i=0;i<b;i++){
          //  sort(vy[i].begin() , vy[i].end(),ff2);
            int cou=0;
        for(int j=0;j<vy[i].size();j++){
            if(c[vy[i][j].i]==0){
            c[vy[i][j].i]=1;
            cou++;
            c2++;
            }
            if(cou==k)
                break;
        }
      //  for(int j=0;j<n;j++){
      //      cout<<c[j]<<" ";
      //  }
      //  cout<<endl;
  //  cout<<endl;
    }

   // cout<<c2<<endl;
   // cout<<"k   "<<k<<endl;
    if(c2==n){
        ans=min(ans,k);
        r=k-1;
    }
    else
        l=k+1;
 //cout<<ans<<endl;
    }

    return ans;
}

Compilation message (stderr)

robots.cpp: In function 'bool ff(diplo, diplo)':
robots.cpp:15:32: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
     return x.y>y.y || x.y==y.y && x.x>y.x;
                       ~~~~~~~~~^~~~~~~~~~
robots.cpp: In function 'bool ff2(diplo, diplo)':
robots.cpp:19:32: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
     return x.x>y.x || x.x==y.x && x.y>y.y;
                       ~~~~~~~~~^~~~~~~~~~
robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:118:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<vx[i].size();j++){
                     ~^~~~~~~~~~~~~
robots.cpp:137:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<vy[i].size();j++){
                     ~^~~~~~~~~~~~~

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