Omówienie zadania “Modern Art 2”

Omówienie zadania “Modern Art 2”

Szczegółowe omówienie zadania Modern Art 2 z dywizji Gold Amerykańskiej Olimpiady Informatycznej USACO:

Link do zadania:
Zadanie wymaga jedynie pomysłu i jest świetnym przygotowaniem do Olimpiad i konkursów informatycznych.
——-
Poniżej kod wzorcowy zadania “Modern Art 2” użyty w powyższym omówieniu.

#include <bits/stdc++.h>
using namespace std;

const int MAX_PIXELS = 1e5+7;
int pixels[MAX_PIXELS];
int colors_start[MAX_PIXELS];
int colors_end[MAX_PIXELS];
int pixel_stack[MAX_PIXELS];

int main() {
 ios_base::sync_with_stdio(0);
 cin.tie(0);
 cout.tie(0);

 freopen("art2.in", "r", stdin);
 freopen("art2.out", "w", stdout);

 int number_of_pixels;
 int max_depth;
 int stack_depth;
 int i;

 cin >> number_of_pixels;

 for (i=1; i<=number_of_pixels; ++i) {
    cin >> pixels[i];
    if ( colors_start[ pixels[i] ] == 0 ) {
       colors_start[ pixels[i] ] = i;
	}
    colors_end[ pixels[i] ] = i;
 }
 number_of_pixels += 2;
 colors_start[0] = 0;
 colors_end[0] = number_of_pixels-1;

 stack_depth = max_depth = 0;
 for (i=0; i<number_of_pixels; ++i) {
    if (colors_start[ pixels[i] ] == i) {
       pixel_stack[stack_depth]	= pixels[i];
       ++stack_depth;
       max_depth = max(max_depth,stack_depth);
	}
    if (colors_end[ pixels[i] ] == i) {
       --stack_depth;
	   if (pixel_stack[stack_depth]	!= pixels[i]) {
	      cout << "-1\n";
		  return 0;	
	   }
	}
 }

 --max_depth;
 cout << max_depth;

 return 0;
}
Link do pobrania pliku z kodem C++ zadania "Modert Art 2"

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz