Submission #1101425

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101425		alexander707070	Robots (IOI13_robots)	C++14	Compilation error	0 ms	0 KiB

robots

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

#define MAXN 30007
using namespace std;

struct edge{
    int to;
    bool cap;
    int rev;
};

struct toy{
    int x,y,id;
};

int n,m,k;
int x[MAXN],y[MAXN];
toy s[MAXN],t[MAXN];

bool cmp(toy fr,tyo sc){
    return fr.x<sc.x;
}

bool cmp2(toy fr,tyo sc){
    return fr.y<sc.y;
}

vector<edge> g[MAXN];

void add_edge(int from,int to){
    g[from].push_back({to,1,int(g[to].size())});
    g[to].push_back({from,0,int(g[from].size())-1});
}

int source,sink,flow,maxflow;
int li[MAXN],tim;

int dfs(int x){
    if(x==sink)return 1;

    li[x]=tim;
    for(int i=0;i<g[x].size();i++){
        if(li[g[x][i].to]==tim or !g[x][i].cap)continue;

        int curr=dfs(g[x][i].to);
        if(curr>0){
            g[x][i].cap=false;
            g[g[x][i].to][g[x][i].rev].cap=true;
            return 1;
        }
    }

    return 0;
}

int cnt[MAXN],cnt2[MAXN];
bool is[MAXN];

bool greedy(int days){
    for(int i=1;i<=10;i++){

        for(int i=1;i<=n;i++)cnt[i]=days;
        for(int f=1;f<=m;f++)cnt2[i]=days;

        random_shuffle(t+1,t+k+1);
        for(int f=1;f<=k;f++)is[f]=false;

        for(int f=1;f<=k;f++){
            for(int d=1;d<=n;d++){
                if(x[d]>s[f].first and cnt[d]>0){
                    cnt[d]--; is[f]=true; 
                    break;
                }
            }
        }

        for(int f=1;f<=k;f++){
            if(is[f])continue;

            for(int d=1;d<=m;d++){
                if(y[d]>s[f].second and cnt2[d]>0){
                    cnt2[d]--; is[f]=true;
                    break;
                }
            }
        }

        for(int f=1;f<=k;f++){
            if(!is[f])break;
            if(f==k)return true;
        }
    }

    return false;
}

bool check(int days){

    if(greedy(days))return true;
    sort(t+1,t+k+1,cmp2);

    int A=min(n*days,k);
    int B=min(m*days,k);

    source=0; sink=A+B+k+1;
    for(int i=0;i<=sink;i++)g[i].clear();

    for(int i=1;i<=A+B;i++)add_edge(source,i);
    for(int i=1;i<=k;i++)add_edge(A+B+i,sink);

    int pt=0;
    for(int i=n;i>=1;i--){
        for(int t=1;t<=days;t++){
            pt++;
            if(pt>k)break;

            for(int f=1;f<=k-pt+1;f++){
                if(x[i]<=s[f].x)continue;
                add_edge(pt,A+B+s[f].id);
            }
        }
    }

    pt=0;
    for(int i=m;i>=1;i--){
        for(int t=1;t<=days;t++){
            pt++;
            if(pt>k)break;

            for(int f=1;f<=k-pt+1;f++){
                if(y[i]<=t[f].y)continue;
                add_edge(A+pt,A+B+t[f].id);
            }
        }
    }

    maxflow=0;
    while(true){
        tim++;
        flow=dfs(source);

        if(flow==0)break;
        maxflow+=flow;
    }

    return maxflow==k;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
//int putaway(int A, int B, int T, vector<int> X, vector<int> Y, vector<int> W, vector<int> S) {
    n=A; m=B; k=T;

    for(int i=1;i<=n;i++)x[i]=X[i-1];
    for(int i=1;i<=m;i++)y[i]=Y[i-1];
    for(int i=1;i<=k;i++)s[i]=t[i]={W[i-1],S[i-1],i};

    sort(x+1,x+n+1);
    sort(y+1,y+m+1);

    sort(s+1,s+k+1,cmp);
    sort(t+1,t+k+1,cmp2);

    if(x[n]<=s[k].first and y[m]<=s[k].second)return -1;

    int l=0,r=k+1,tt;
    while(l+1<r){
        tt=(l+r)/2;
 
        if(check(tt))r=tt;
        else l=tt;
    }

    return r;
}


/*int main(){

    cout<<putaway(3,2,10,{6,2,9},{4,7},{4,8,2,7,1,5,3,8,7,10},{6,5,3,9,8,1,3,7,6,5})<<"\n";

	return 0;
}*/

Compilation message (stderr)

robots.cpp:21:17: error: 'tyo' has not been declared
   21 | bool cmp(toy fr,tyo sc){
      |                 ^~~
robots.cpp: In function 'bool cmp(toy, int)':
robots.cpp:22:20: error: request for member 'x' in 'sc', which is of non-class type 'int'
   22 |     return fr.x<sc.x;
      |                    ^
robots.cpp: At global scope:
robots.cpp:25:18: error: 'tyo' has not been declared
   25 | bool cmp2(toy fr,tyo sc){
      |                  ^~~
robots.cpp: In function 'bool cmp2(toy, int)':
robots.cpp:26:20: error: request for member 'y' in 'sc', which is of non-class type 'int'
   26 |     return fr.y<sc.y;
      |                    ^
robots.cpp: In function 'int dfs(int)':
robots.cpp:43:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int i=0;i<g[x].size();i++){
      |                 ~^~~~~~~~~~~~
robots.cpp: In function 'bool greedy(int)':
robots.cpp:71:30: error: 'struct toy' has no member named 'first'
   71 |                 if(x[d]>s[f].first and cnt[d]>0){
      |                              ^~~~~
robots.cpp:82:30: error: 'struct toy' has no member named 'second'
   82 |                 if(y[d]>s[f].second and cnt2[d]>0){
      |                              ^~~~~~
robots.cpp: In function 'bool check(int)':
robots.cpp:132:27: error: invalid types 'int[int]' for array subscript
  132 |                 if(y[i]<=t[f].y)continue;
      |                           ^
robots.cpp:133:36: error: invalid types 'int[int]' for array subscript
  133 |                 add_edge(A+pt,A+B+t[f].id);
      |                                    ^
robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:164:19: error: 'struct toy' has no member named 'first'
  164 |     if(x[n]<=s[k].first and y[m]<=s[k].second)return -1;
      |                   ^~~~~
robots.cpp:164:40: error: 'struct toy' has no member named 'second'
  164 |     if(x[n]<=s[k].first and y[m]<=s[k].second)return -1;
      |                                        ^~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from robots.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = toy*; _Iterator2 = toy*; _Compare = bool (*)(toy, int)]':
/usr/include/c++/10/bits/stl_algo.h:82:17:   required from 'void std::__move_median_to_first(_Iterator, _Iterator, _Iterator, _Iterator, _Compare) [with _Iterator = toy*; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(toy, int)>]'
/usr/include/c++/10/bits/stl_algo.h:1924:34:   required from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = toy*; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(toy, int)>]'
/usr/include/c++/10/bits/stl_algo.h:1958:38:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = toy*; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(toy, int)>]'
/usr/include/c++/10/bits/stl_algo.h:1974:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = toy*; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(toy, int)>]'
/usr/include/c++/10/bits/stl_algo.h:4892:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = toy*; _Compare = bool (*)(toy, int)]'
robots.cpp:101:24:   required from here
/usr/include/c++/10/bits/predefined_ops.h:156:30: error: cannot convert 'toy' to 'int' in argument passing
  156 |         { return bool(_M_comp(*__it1, *__it2)); }
      |                       ~~~~~~~^~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Val_comp_iter<_Compare>::operator()(_Value&, _Iterator) [with _Value = toy; _Iterator = toy*; _Compare = bool (*)(toy, int)]':
/usr/include/c++/10/bits/stl_algo.h:1826:20:   required from 'void std::__unguarded_linear_insert(_RandomAccessIterator, _Compare) [with _RandomAccessIterator = toy*; _Compare = __gnu_cxx::__ops::_Val_comp_iter<bool (*)(toy, int)>]'
/usr/include/c++/10/bits/stl_algo.h:1854:36:   required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = toy*; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(toy, int)>]'
/usr/include/c++/10/bits/stl_algo.h:1886:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = toy*; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(toy, int)>]'
/usr/include/c++/10/bits/stl_algo.h:1977:31:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = toy*; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(toy, int)>]'
/usr/include/c++/10/bits/stl_algo.h:4892:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = toy*; _Compare = bool (*)(toy, int)]'
robots.cpp:101:24:   required from here
/usr/include/c++/10/bits/predefined_ops.h:238:23: error: cannot convert 'toy' to 'int' in argument passing
  238 |  { return bool(_M_comp(__val, *__it)); }
      |                ~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_comp_val<_Compare>::operator()(_Iterator, _Value&) [with _Iterator = toy*; _Value = toy; _Compare = bool (*)(toy, int)]':
/usr/include/c++/10/bits/stl_heap.h:139:48:   required from 'void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare&) [with _RandomAccessIterator = toy*; _Distance = long int; _Tp = toy; _Compare = __gnu_cxx::__ops::_Iter_comp_val<bool (*)(toy, int)>]'
/usr/include/c++/10/bits/stl_heap.h:246:23:   required from 'void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = toy*; _Distance = long int; _Tp = toy; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(toy, int)>]'
/usr/include/c++/10/bits/stl_heap.h:355:22:   required from 'void std::__make_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare&) [with _RandomAccessIterator = toy*; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(toy, int)>]'
/usr/include/c++/10/bits/stl_algo.h:1666:23:   required from 'void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = toy*; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(toy, int)>]'
/usr/include/c++/10/bits/stl_algo.h:1937:25:   required from 'void std::__partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = toy*; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(toy, int)>]'
/usr/include/c++/10/bits/stl_algo.h:1953:27:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = toy*; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(toy, int)>]'
/usr/include/c++/10/bits/stl_algo.h:1974:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = toy*; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(toy, int)>]'
/usr/include/c++/10/bits/stl_algo.h:4892:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = toy*; _Compare = bool (*)(toy, int)]'
robots.cpp:101:24:   required from here
/usr/include/c++/10/bits/predefined_ops.h:194:23: error: cannot convert 'toy' to 'int' in argument passing
  194 |  { return bool(_M_comp(*__it, __val)); }
      |                ~~~~~~~^~~~~~~~~~~~~~