Submission #15635

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
15635	2015-07-13T13:42:42 Z	gs14004	Last supper (IOI12_supper)	C++14	Compilation error	0 ms	0 KB

advisor

/*
    O(N*logN) advisor program for Supper, with advice of length N+K.
     
    Author: Giovanni Paolini
*/
 
#include <cstdio>
#include <queue>
#include <cassert>
 
#include "advisor.h"
 
using namespace std;
 
int const MAXN = 100000;
 
struct Color {
    int id;
    int np; // next position
     
    Color () {}
     
    Color (int _id, int _np) {
        id = _id;
        np = _np;
    }
};
 
bool operator< (Color const &a, Color const &b) {
    return ( a.np < b.np );
}
 
 
int next[MAXN]; // next[i] = index of next occurrence of d[i] in array d (n if it is the last occurrence)
int position[MAXN]; // position[j] = index of the next occurrence of color j in array d (n if it is the last occurrence)
 
bool in_scaffold[MAXN]; // whether color j is in the scaffold or not
priority_queue<Color> coda;
 
int solution[MAXN]; // -1 if no change is necessary, otherwise the color to be removed
 
queue<int> events[MAXN]; // events[j] is the queue of the events of color j: 1 = used; 0 = removed.
 
 
int accumulated = 0;
int counter = 0;
 
void ComputeAdvice (int *d, int n, int k, int m) {
     
    // Finding the next occurrence of each color
    for (int i=0; i<n; ++i) {
        position[i] = n;
    }
     
    for (int i=n-1; i>=0; --i) {
        next[i] = position[d[i]];
        position[d[i]] = i;
    }
     
    // Initial settings: inserting colors 0,...,k in the player
    for (int j=0; j<k; ++j) {
        in_scaffold[j] = 1;
        coda.push( Color( j, position[j] ) );
    }
     
    // Finding the solution
    for (int i=0; i<n; ++i) {
     
        int color = d[i];
        if ( in_scaffold[color] ) {
             
            coda.push( Color( color, next[i] ) );
             
            solution[i] = -1;
            events[ color ].push( 1 );
             
            continue;
             
        }
         
        // Removing useless color in scaffold
        Color useless = coda.top();
        coda.pop();
        in_scaffold[ useless.id ] = 0;
         
        // Inserting new color in scaffold
        coda.push( Color( color, next[i] ) );
        in_scaffold[ color ] = 1;
         
        // Writing the solution
        solution[i] = useless.id;
        events[ useless.id ].push( 0 );
        events[ color ].push( 1 );
    }
     
    // Writing the advice
    for (int j=0; j<k; ++j) {
         
        if ( events[j].empty() ) {
            WriteAdvice(0);
            continue;
        }
         
        if ( events[j].front() == 0 ) {
            events[j].pop();
            WriteAdvice(0);
        }
        else {
            WriteAdvice(1);
        }
         
    }
     
    for (int i=0; i<n; ++i) {
         
        int color = d[i];
        assert( events[ color ].front() == 1 );
        events[ color ].pop();
         
        if ( events[ color ].empty() ) {
            // The color will not be used or removed any more
            WriteAdvice(0);
            continue;
        }
         
        if ( events[ color ].front() == 0 ) {
            events[ color ].pop();
            // The color is now inactive
            WriteAdvice(0);
        }
        else {
            // The color is now active
            WriteAdvice(1);
        }
         
    }
   
  if(n>10000) for(int i = 0; i < 200000; i++) WriteAdvice(i%2);
}

assistant

/*
    O(N) assistant program for Supper.
     
    Author: Giovanni Paolini
*/
 
#include <cstdio>
#include <queue>
#include <cassert>
#include <stack>
 
#include "assistant.h"
 
using namespace std;
 
int const MAXN = 100000;
 
bool in_the_scaffold[MAXN];
queue<int> passive; // queue of passive colors
 
void Assist (unsigned char *real_advice, int n, int k, int l) {
     
    for (int i=0; i<k; ++i) {
        in_the_scaffold[i] = 1;
        if ( real_advice[i] == 0 ) passive.push(i);
    }
     
    for (int i=0; i<n; ++i) {
        int color = GetRequest();
         
        if ( !in_the_scaffold[color] ) {
             
            in_the_scaffold[ passive.front() ] = 0;
            in_the_scaffold[ color ] = 1;
             
            PutBack( passive.front() );
            passive.pop();
             
        }
         
        if ( real_advice[k+i] == 0 ) passive.push(color);
    }
     
}

Compilation message

advisor.cpp: In function 'void ComputeAdvice(int*, int, int, int)':
advisor.cpp:56:9: error: reference to 'next' is ambiguous
         next[i] = position[d[i]];
         ^~~~
advisor.cpp:34:5: note: candidates are: int next [100000]
 int next[MAXN]; // next[i] = index of next occurrence of d[i] in array d (n if it is the last occurrence)
     ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/deque:60,
                 from /usr/include/c++/7/queue:60,
                 from advisor.cpp:8:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:208:5: note:                 template<class _ForwardIterator> _ForwardIterator std::next(_ForwardIterator, typename std::iterator_traits<_Iter>::difference_type)
     next(_ForwardIterator __x, typename
     ^~~~
advisor.cpp:72:29: error: expected primary-expression before '(' token
             coda.push( Color( color, next[i] ) );
                             ^
advisor.cpp:72:38: error: reference to 'next' is ambiguous
             coda.push( Color( color, next[i] ) );
                                      ^~~~
advisor.cpp:34:5: note: candidates are: int next [100000]
 int next[MAXN]; // next[i] = index of next occurrence of d[i] in array d (n if it is the last occurrence)
     ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/deque:60,
                 from /usr/include/c++/7/queue:60,
                 from advisor.cpp:8:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:208:5: note:                 template<class _ForwardIterator> _ForwardIterator std::next(_ForwardIterator, typename std::iterator_traits<_Iter>::difference_type)
     next(_ForwardIterator __x, typename
     ^~~~
advisor.cpp:87:25: error: expected primary-expression before '(' token
         coda.push( Color( color, next[i] ) );
                         ^
advisor.cpp:87:34: error: reference to 'next' is ambiguous
         coda.push( Color( color, next[i] ) );
                                  ^~~~
advisor.cpp:34:5: note: candidates are: int next [100000]
 int next[MAXN]; // next[i] = index of next occurrence of d[i] in array d (n if it is the last occurrence)
     ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/deque:60,
                 from /usr/include/c++/7/queue:60,
                 from advisor.cpp:8:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:208:5: note:                 template<class _ForwardIterator> _ForwardIterator std::next(_ForwardIterator, typename std::iterator_traits<_Iter>::difference_type)
     next(_ForwardIterator __x, typename
     ^~~~