Submission #1143

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1143	2013-06-27T19:36:22 Z	tncks0121	Last supper (IOI12_supper)	C++	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:3: 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:20: error: expected primary-expression before '(' token
    coda.push( Color( color, next[i] ) );
                    ^
advisor.cpp:72:29: 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:19: error: expected primary-expression before '(' token
   coda.push( Color( color, next[i] ) );
                   ^
advisor.cpp:87:28: 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
     ^~~~