Submission #134371

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
134371	2019-07-22T13:52:15 Z	rajarshi_basu	Olympiads (BOI19_olympiads)	C++14	Compilation error	0 ms	0 KB

olympiads

#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <fstream>
#include <complex>
#include <random>
#include <stack>
#include <chrono>
#include <set>
 
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define ff first
#define il pair<int,ll>
#define li pair<ll,int>
#define ss second
#define pll pair<ll,ll>
#define cd complex<double> 
#define ld long double
#define pld pair<ld,ld>
#define iii pair<ii,ll>
#define vv vector
 
using namespace std;
 
const int MAXN = 501;
 
int n,k;
vv<int> all[MAXN];
multiset<int,greater<int> > allV;
 
// for subspace : 1 = taken, 0 = not to be taken. 2 = can be either.
 
 
 
struct data{
    int* arr;
    int sum;
    data(int* a,int s){
        arr = a;
        sum = s;
    }
};
 
bool comp(data& d1, data& d2){
    return d1.sum < d2.sum;
}
 
//queue<int*> q;
priority_queue<data,vector<data>, function<bool(data,data)> > pq(comp);
 
int evaluateSpace(int* arr,vi& ans){
    //cout << "ENTERED" << endl;
    //FOR(i,n)cout << arr[i] << " ";cout << endl;
    vi valid;
    vi taken;
    FOR(i,n){
        if(arr[i] == 2)valid.pb(i);
        else if(arr[i] == 1)taken.pb(i);
    }
    if(taken.size() == k){
        int xx[k];
        FOR(i,k)xx[i] = 0;
           
        for(auto e : taken){
            FOR(i,k)xx[i] = max(xx[i],all[e][i]);
        }
        int sum = 0;
        FOR(i,k)sum += xx[i];
            
        return sum;
    }
    if(valid.size() == 0)return 0;

    int numT = k - taken.size();
    if(valid.size() < numT){
        return 0;
    }
    set<int> goood;
    FOR(sortItem,k){
        if(valid.size() == 0)break;
        sort(valid.begin(), valid.end(),[&](int a,int b){
            if(goood.find(a) != goood.end())return false;
            if(goood.find(b) != goood.end())return true;
            return all[a][sortItem] > all[b][sortItem];
        });
        goood.insert(valid[0]);
    }
    vi good;
    for(auto e : goood)good.pb(e);
 
    int mx = 0;
    
    
    //cout << numT << endl;
    //cout << good.size() << endl;
    
    FOR(mask,1<<good.size()){
        if(numT > good.size())break;
        vi cc;
        FOR(j,good.size()){
            if(((1<<j)&mask) > 0){
                cc.pb(good[j]);
            }
        }
        if(cc.size() == numT){
            // this is a candidate choice
            int sum = 0;
            int xx[k];
            FOR(i,k)xx[i] = 0;
            for(auto e : taken){
                FOR(i,k)xx[i] = max(xx[i],all[e][i]);
            }
            for(auto e : cc){
                FOR(i,k)xx[i] = max(xx[i],all[e][i]);   
            }
            FOR(i,k)sum += xx[i];
            if(sum > mx){
 
                mx = sum;
                ans = cc;
            }
        }
    }

    //cout << "EXITED" << endl;
    return mx;
}
 
void processSubspace(int* space){
    vi ans;
    vi ans2;
    int an;
    try{
        an = evaluateSpace(space,ans);
    }catch(...){
        while(1);
    }
    if(an == 0)return;
    allV.insert(an);
    
    //cout << an << endl;
    // ans now contains the stuff that i am to take.
    FOR(i,ans.size()){
        int* arr = new int[n];
        FOR(j,n)arr[j] = space[j];
        FOR(j,i){
            arr[ans[j]] = 1;
        }
        arr[ans[i]] = 0;
        int x = evaluateSpace(arr,ans2);
        pq.push(data(arr,x));
    }
    ans2.clear();
}
 
void solve(){
    int arr[n];
    FOR(i,n)arr[i] = 2;
    processSubspace(arr);
    while(!pq.empty() and allV.size() < 3000){
        data d = pq.top();pq.pop();
        processSubspace(d.arr);
    }
}
 
int main(){
    int c;
    cin >> n >> k >> c;
    FOR(i,n){
        FOR(j,k){
            int a;
            cin >> a;
            all[i].pb(a);
        }
    }
    solve();

    int ctr = 0;
    for(auto e : allV){
        ctr++;
        if(c == ctr){
 
            cout << e << endl;
            return 0;
        }
        //cout << e << endl;
    }
    return 0;
}

Compilation message

olympiads.cpp:63:70: error: no matching function for call to 'std::priority_queue<data, std::vector<data>, std::function<bool(data, data)> >::priority_queue(bool (&)(data&, data&))'
 priority_queue<data,vector<data>, function<bool(data,data)> > pq(comp);
                                                                      ^
In file included from /usr/include/c++/7/queue:64:0,
                 from olympiads.cpp:9:
/usr/include/c++/7/bits/stl_queue.h:552:2: note: candidate: template<class _InputIterator> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(_InputIterator, _InputIterator, const _Compare&, _Sequence&&)
  priority_queue(_InputIterator __first, _InputIterator __last,
  ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_queue.h:552:2: note:   template argument deduction/substitution failed:
olympiads.cpp:63:70: note:   candidate expects 4 arguments, 1 provided
 priority_queue<data,vector<data>, function<bool(data,data)> > pq(comp);
                                                                      ^
In file included from /usr/include/c++/7/queue:64:0,
                 from olympiads.cpp:9:
/usr/include/c++/7/bits/stl_queue.h:541:2: note: candidate: template<class _InputIterator> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(_InputIterator, _InputIterator, const _Compare&, const _Sequence&)
  priority_queue(_InputIterator __first, _InputIterator __last,
  ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_queue.h:541:2: note:   template argument deduction/substitution failed:
olympiads.cpp:63:70: note:   candidate expects 4 arguments, 1 provided
 priority_queue<data,vector<data>, function<bool(data,data)> > pq(comp);
                                                                      ^
In file included from /usr/include/c++/7/queue:64:0,
                 from olympiads.cpp:9:
/usr/include/c++/7/bits/stl_queue.h:509:2: note: candidate: template<class _Alloc, class _Requires> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(std::priority_queue<_Tp, _Sequence, _Compare>&&, const _Alloc&)
  priority_queue(priority_queue&& __q, const _Alloc& __a)
  ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_queue.h:509:2: note:   template argument deduction/substitution failed:
olympiads.cpp:63:70: note:   candidate expects 2 arguments, 1 provided
 priority_queue<data,vector<data>, function<bool(data,data)> > pq(comp);
                                                                      ^
In file included from /usr/include/c++/7/queue:64:0,
                 from olympiads.cpp:9:
/usr/include/c++/7/bits/stl_queue.h:505:2: note: candidate: template<class _Alloc, class _Requires> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(const std::priority_queue<_Tp, _Sequence, _Compare>&, const _Alloc&)
  priority_queue(const priority_queue& __q, const _Alloc& __a)
  ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_queue.h:505:2: note:   template argument deduction/substitution failed:
olympiads.cpp:63:70: note:   candidate expects 2 arguments, 1 provided
 priority_queue<data,vector<data>, function<bool(data,data)> > pq(comp);
                                                                      ^
In file included from /usr/include/c++/7/queue:64:0,
                 from olympiads.cpp:9:
/usr/include/c++/7/bits/stl_queue.h:501:2: note: candidate: template<class _Alloc, class _Requires> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(const _Compare&, _Sequence&&, const _Alloc&)
  priority_queue(const _Compare& __x, _Sequence&& __c, const _Alloc& __a)
  ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_queue.h:501:2: note:   template argument deduction/substitution failed:
olympiads.cpp:63:70: note:   candidate expects 3 arguments, 1 provided
 priority_queue<data,vector<data>, function<bool(data,data)> > pq(comp);
                                                                      ^
In file included from /usr/include/c++/7/queue:64:0,
                 from olympiads.cpp:9:
/usr/include/c++/7/bits/stl_queue.h:496:2: note: candidate: template<class _Alloc, class _Requires> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(const _Compare&, const _Sequence&, const _Alloc&)
  priority_queue(const _Compare& __x, const _Sequence& __c,
  ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_queue.h:496:2: note:   template argument deduction/substitution failed:
olympiads.cpp:63:70: note:   candidate expects 3 arguments, 1 provided
 priority_queue<data,vector<data>, function<bool(data,data)> > pq(comp);
                                                                      ^
In file included from /usr/include/c++/7/queue:64:0,
                 from olympiads.cpp:9:
/usr/include/c++/7/bits/stl_queue.h:492:2: note: candidate: template<class _Alloc, class _Requires> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(const _Compare&, const _Alloc&)
  priority_queue(const _Compare& __x, const _Alloc& __a)
  ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_queue.h:492:2: note:   template argument deduction/substitution failed:
olympiads.cpp:63:70: note:   candidate expects 2 arguments, 1 provided
 priority_queue<data,vector<data>, function<bool(data,data)> > pq(comp);
                                                                      ^
In file included from /usr/include/c++/7/queue:64:0,
                 from olympiads.cpp:9:
/usr/include/c++/7/bits/stl_queue.h:488:2: note: candidate: template<class _Alloc, class _Requires> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(const _Alloc&)
  priority_queue(const _Alloc& __a)
  ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_queue.h:488:2: note:   template argument deduction/substitution failed:
/usr/include/c++/7/bits/stl_queue.h:482:7: note: candidate: std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(const _Compare&, _Sequence&&) [with _Tp = data; _Sequence = std::vector<data>; _Compare = std::function<bool(data, data)>]
       priority_queue(const _Compare& __x, _Sequence&& __s = _Sequence())
       ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_queue.h:482:7: note:   no known conversion for argument 1 from 'bool(data&, data&)' to 'const std::function<bool(data, data)>&'
/usr/include/c++/7/bits/stl_queue.h:477:7: note: candidate: std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(const _Compare&, const _Sequence&) [with _Tp = data; _Sequence = std::vector<data>; _Compare = std::function<bool(data, data)>]
       priority_queue(const _Compare& __x, const _Sequence& __s)
       ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_queue.h:477:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/7/bits/stl_queue.h:473:2: note: candidate: template<class _Seq, class _Requires> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue()
  priority_queue()
  ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_queue.h:473:2: note:   template argument deduction/substitution failed:
olympiads.cpp:63:70: note:   candidate expects 0 arguments, 1 provided
 priority_queue<data,vector<data>, function<bool(data,data)> > pq(comp);
                                                                      ^
In file included from /usr/include/c++/7/queue:64:0,
                 from olympiads.cpp:9:
/usr/include/c++/7/bits/stl_queue.h:423:11: note: candidate: std::priority_queue<data, std::vector<data>, std::function<bool(data, data)> >::priority_queue(const std::priority_queue<data, std::vector<data>, std::function<bool(data, data)> >&)
     class priority_queue
           ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_queue.h:423:11: note:   no known conversion for argument 1 from 'bool(data&, data&)' to 'const std::priority_queue<data, std::vector<data>, std::function<bool(data, data)> >&'
/usr/include/c++/7/bits/stl_queue.h:423:11: note: candidate: std::priority_queue<data, std::vector<data>, std::function<bool(data, data)> >::priority_queue(std::priority_queue<data, std::vector<data>, std::function<bool(data, data)> >&&)
/usr/include/c++/7/bits/stl_queue.h:423:11: note:   no known conversion for argument 1 from 'bool(data&, data&)' to 'std::priority_queue<data, std::vector<data>, std::function<bool(data, data)> >&&'
olympiads.cpp: In function 'int evaluateSpace(int*, std::vector<int>&)':
olympiads.cpp:74:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(taken.size() == k){
        ~~~~~~~~~~~~~^~~~
olympiads.cpp:89:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(valid.size() < numT){
        ~~~~~~~~~~~~~^~~~~~
olympiads.cpp:112:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(numT > good.size())break;
            ~~~~~^~~~~~~~~~~~~
olympiads.cpp:19:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,n) for(int i=0;i<n;i++)
olympiads.cpp:114:13:
         FOR(j,good.size()){
             ~~~~~~~~~~~~~      
olympiads.cpp:114:9: note: in expansion of macro 'FOR'
         FOR(j,good.size()){
         ^~~
olympiads.cpp:119:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(cc.size() == numT){
            ~~~~~~~~~~^~~~~~~
olympiads.cpp: In function 'void processSubspace(int*)':
olympiads.cpp:19:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,n) for(int i=0;i<n;i++)
olympiads.cpp:157:9:
     FOR(i,ans.size()){
         ~~~~~~~~~~~~           
olympiads.cpp:157:5: note: in expansion of macro 'FOR'
     FOR(i,ans.size()){
     ^~~