oj.uz

Submission #26610

# Submission time Handle Problem Language Result Execution time Memory
26610 2017-07-03T12:47:22 Z model_code Lollipop (POI11_liz) C
32 / 100
 2000 ms 5996 KB 
/*************************************************************************
 *                                                                       *
 *                    XVIII Olimpiada Informatyczna                      *
 *                                                                       *
 *   Zadanie:           Lizak                                            *
 *   Autor:             Mateusz Baranowski                               *
 *   Zlozonosc czasowa: O(n * m * lg(n))                                 *
 *          pamieciowa: O(n)                                             *
 *   Opis:              Rozwiazanie powolne                              *
 *                      Rozwiazanie przez bisekcje                       *
 *                                                                       *
 *************************************************************************/

#include <stdio.h>
#define MAX_N 1000000

int n, m;	/* ilosc segmentow lizaka i ilosc rozwazanych cen */
int sum[MAX_N + 1]; /* sum[i] cena fragmentu [1, i] */
int i, l, k;
int max[2];	/* najwieksza cena parzysta i nieparzysta */
int a, b, c; /* poczatek, koniec i srodek rozwazanego przedzialu */
int wa, wb; /* przedzial wynikowy */
char s[MAX_N + 1];	/* opis lizaka */

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

	sum[0] = 0;
	for (i = 0; i < n; ++i)
		if (s[i] == 'W')
			sum[i + 1] = sum[i] + 1;
		else
			sum[i + 1] = sum[i] + 2;
	
	for (i = 0; i < m ; ++i) {
		scanf ("%d", &k);
		wa = 0;
		if (k <= sum[n]) {
			l = 0;
			while ((wa == 0) && (l < n)) {
				/* przeszukiwanie binarne konca przedzialu dla poczatku l */
				a = l;
				b = n;
				while (a < b) {
					c = (a + b) / 2;
					if (sum[c] - sum[l] < k)
						a = c + 1;
					else if (sum[c] - sum[l] > k)
						b = c - 1;
					else {
						a = c;
						b = c;
					}
				}

				if (sum[a] - sum[l] == k) {
					wa = l + 1;
					wb = a;
				}
				++l;
			}
		}
		if (wa != 0)
			printf("%d %d\n", wa, wb);
		else
			printf("NIE\n");
	}

	return 0;
}

Compilation message

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5996 KB Output is correct
2 Correct 0 ms 5996 KB Output is correct
3 Correct 0 ms 5996 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5996 KB Output is correct
2 Correct 0 ms 5996 KB Output is correct
3 Correct 0 ms 5996 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5996 KB Output is correct
2 Correct 0 ms 5996 KB Output is correct
3 Correct 43 ms 5996 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5996 KB Output is correct
2 Correct 49 ms 5996 KB Output is correct
3 Correct 6 ms 5996 KB Output is correct

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 5996 KB Output is correct
2 Correct 13 ms 5996 KB Output is correct
3 Execution timed out 2000 ms 5996 KB Execution timed out

Subtask #6
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 5996 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 5996 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 5996 KB Output is correct
2 Execution timed out 2000 ms 5996 KB Execution timed out
3 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 5996 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 5996 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 5996 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 5996 KB Execution timed out
2 Halted 0 ms 0 KB -