oj.uz

답안 #26600

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
26600 2017-07-03T12:28:23 Z model_code Lollipop (POI11_liz) C
100 / 100
 639 ms 17720 KB 
/*************************************************************************
 *                                                                       *
 *                    XVIII Olimpiada Informatyczna                      *
 *                                                                       *
 *   Zadanie:           Lizak                                            *
 *   Autor:             Mateusz Baranowski                               *
 *   Zlozonosc czasowa: O(n + m)                                         *
 *          pamieciowa: O(n)                                             *
 *   Opis:              Rozwiazanie wzorcowe                             *
 *                                                                       *
 *************************************************************************/

#include <stdio.h>
#define MAX_N 1000000
#define MAX_K 2000000

int n, m;	/* ilosc segmentow lizaka i ilosc rozwazanych cen */
int wa[MAX_K + 1], wb[MAX_K + 1]; /* [wa[j], wb[j]] to przedzial o koszcie j */
int i, l, sum = 0;
int max[2];	/* najwieksza cena parzysta i nieparzysta */
char s[MAX_N + 1];	/* opis lizaka */

/* funkcja obliczajaca wa[x], wb[x] dla (x <= sum) i ((sum + x) mod 2 == 0) */
void oblicz_przedzialy(int sum) {
	wa[sum] = i + 1;
	wb[sum] = l + 1;

	while (sum > 2) {
		while ((sum > 2) && (s[i] == 'T')) {
			sum -= 2;
			wa[sum] = ++i + 1;
			wb[sum] = l + 1;
		}
		while ((sum > 2) && (s[l] == 'T')) {
			sum -= 2;
			wa[sum] = i + 1;
			wb[sum] = --l + 1;
		}
		
		if (sum > 2) {
			sum -= 2;
			wa[sum] = ++i + 1;
			wb[sum] = --l + 1;
		}
	}
}

int main() {
	scanf("%d %d", &n, &m);
	scanf("%s", s);

	for (l = 0; l < n; ++l)
		if (s[l] == 'T')
			sum += 2;
		else
			sum += 1;
	
	i = 0;
	l = n - 1;
	max[sum % 2] = sum;
	
	oblicz_przedzialy(sum);

	/* szukamy 'W' najblizszego krawedzi lizaka by wyznaczyc najwiekszy *
	 * fragment, ktorego cena ma inna parzystosc niz cena calego lizaka */
	i = 0;
	while ((i < n) && (s[i] == 'T'))
		++i;

	l = 0;
	while ((i < n - l) && (s[n - l - 1] == 'T'))
		++l;
	
	if (s[i] == 'T') /* brak smaku waniliowego */
		max[1] = 0;
	else {
		if (i < l) { /* 'W' blizej lewego konca */
			sum -= 2 * i + 1;
			max[sum % 2] = sum;
			i += 1;
			l = n - 1;
		} else { /* 'W' blizej prawego konca (lub rownie blisko) */
			sum -= 2 * l + 1;
			max[sum % 2] = sum; 	
			i = 0;
			l = n - l - 2;
		}

		oblicz_przedzialy(sum);
	}

	/* odpowiadamy na zapytania korzystajac z tablic wa[] i wb[] */
	for (i = 0; i < m; ++i) {
		scanf("%d", &sum);

		if (max[sum % 2] < sum)
			printf("NIE\n");
		else
			printf("%d %d\n", wa[sum], wb[sum]);
	}

	return 0;
}

Compilation message

liz.c: In function 'main':
liz.c:49:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ^
liz.c:50:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", s);
  ^
liz.c:94:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &sum);
   ^

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 17720 KB Output is correct
2 Correct 0 ms 17720 KB Output is correct
3 Correct 0 ms 17720 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 17720 KB Output is correct
2 Correct 0 ms 17720 KB Output is correct
3 Correct 0 ms 17720 KB Output is correct

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 17720 KB Output is correct
2 Correct 0 ms 17720 KB Output is correct
3 Correct 9 ms 17720 KB Output is correct

Subtask #4
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 17720 KB Output is correct
2 Correct 3 ms 17720 KB Output is correct
3 Correct 3 ms 17720 KB Output is correct

Subtask #5
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 17720 KB Output is correct
2 Correct 6 ms 17720 KB Output is correct
3 Correct 26 ms 17720 KB Output is correct

Subtask #6
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 17720 KB Output is correct
2 Correct 209 ms 17720 KB Output is correct
3 Correct 76 ms 17720 KB Output is correct

Subtask #7
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 17720 KB Output is correct
2 Correct 43 ms 17720 KB Output is correct
3 Correct 86 ms 17720 KB Output is correct

Subtask #8
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 159 ms 17720 KB Output is correct
2 Correct 93 ms 17720 KB Output is correct
3 Correct 173 ms 17720 KB Output is correct

Subtask #9
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 366 ms 17720 KB Output is correct
2 Correct 303 ms 17720 KB Output is correct
3 Correct 339 ms 17720 KB Output is correct

Subtask #10
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 309 ms 17720 KB Output is correct
2 Correct 443 ms 17720 KB Output is correct
3 Correct 489 ms 17720 KB Output is correct

Subtask #11
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 639 ms 17720 KB Output is correct
2 Correct 596 ms 17720 KB Output is correct
3 Correct 523 ms 17720 KB Output is correct

Subtask #12
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 553 ms 17720 KB Output is correct
2 Correct 536 ms 17720 KB Output is correct
3 Correct 403 ms 17720 KB Output is correct