oj.uz

Submission #29522

# Submission time Handle Problem Language Result Execution time Memory
29522 2017-07-20T05:01:00 Z 윤교준(#1243) Lollipop (POI11_liz) C++11
0 / 100
 729 ms 49872 KB 
#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[sz(V)-2])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define rgiv(V,n) ((V)[((n)+sz(V))%sz(V)])
#define clv(V) (V).clear()
#define upmax(a,b) (a)=max((a),(b))
#define INF (0x3f3f3f3f)
#define MAXN (1000005)
#define MAXX (2000005)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

char str[MAXN];
pii PT[MAXX];
pii T[MAXN];
int EX[MAXX];
int S[MAXN];

pii Ans[MAXN];
int Q[MAXN];
int N, M;

void ctc() {
	const int MX = N * 2;
	for(int i = 1; i <= M; i++) {
		if(MX < Q[i] || (Q[i]&1)) Ans[i] = {-1, -1};
		else Ans[i] = {1, Q[i]/2};
	}
}
void process() {
	int widx = -1;
	for(int i = 1; i <= N; i++) {
		if('W' == str[i]) {
			widx = i; break;
		}
	}
	if(-1 == widx) { ctc(); return; }
	for(int i = widx; i <= N; i++) str[i-widx+1] = str[i];
	N -= widx-1;
	fill(EX, EX+MAXX, -1);
	T[1] = {1, 1}; EX[1] = 1;
	for(int i = 2; i <= N; i++) {
		if('W' == str[i]) T[i] = {T[i-1].second+1, T[i-1].second+1};
		else T[i] = {T[i-1].second+1, T[i-1].second+2};
		EX[T[i].first] = EX[T[i].second] = i;
	}
	fill(PT, PT+MAXX, (pii){-1, -1});
	for(int i = 1; i <= N; i++) S[i] = S[i-1] + ('W' == str[i] ? 1 : 2);
	for(int i = N; ~i; i--) {
		for(int j = 0; j < widx; j++) {
			int num = S[i] + j*2;
			if(-1 != PT[num].first) break;
			PT[num] = {j, i};
		}
	}

	for(int i = 1; i <= M; i++) {
		if(-1 != EX[Q[i]]) {
			int s = 0, e = EX[Q[i]]-1; for(int m; s < e;) {
				m = (s+e)/2;
				int ret = S[EX[Q[i]]] - S[m];
				if(ret == Q[i]) { s = m; break; }
				else if(ret < Q[i]) s = m+1;
				else e = m-1;
			}
			Ans[i] = {s+widx, EX[Q[i]]+widx-1};
		} else if(-1 != PT[Q[i]].first) {
			Ans[i] = {widx - PT[Q[i]].first, PT[Q[i]].second + widx - 1};
		} else Ans[i] = {-1, -1};
	}
}
int main() {
	scanf("%d%d %s", &N, &M, str+1);
	for(int i = 1; i <= M; i++) scanf("%d", &Q[i]);
	process();
	for(int i = 1; i <= M; i++) {
		if(Ans[i].first == -1) puts("NIE");
		else printf("%d %d\n", Ans[i].first, Ans[i].second);
	}
	return 0;
}

Compilation message

liz.cpp: In function 'int main()':
liz.cpp:80:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d %s", &N, &M, str+1);
                                 ^
liz.cpp:81:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= M; i++) scanf("%d", &Q[i]);
                                                ^

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 49872 KB Output is correct
2 Correct 6 ms 49872 KB Output is correct
3 Incorrect 0 ms 49872 KB Oczekiwano przedzialu o koszcie 19 otrzymano przedzial wartosci 2

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 49872 KB Oczekiwano przedzialu o koszcie 22 otrzymano przedzial wartosci 2
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 49872 KB Oczekiwano przedzialu o koszcie 367 otrzymano przedzial wartosci 2
2 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 49872 KB Oczekiwano przedzialu o koszcie 4596 otrzymano przedzial wartosci 2
2 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 49872 KB Oczekiwano przedzialu o koszcie 15416 otrzymano przedzial wartosci 2
2 Halted 0 ms 0 KB -

Subtask #6
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 49872 KB Oczekiwano przedzialu o koszcie 48579 otrzymano przedzial wartosci 2
2 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 49872 KB Oczekiwano przedzialu o koszcie 76689 otrzymano przedzial wartosci 1
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 156 ms 49872 KB Oczekiwano przedzialu o koszcie 29957 otrzymano przedzial wartosci 2
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 336 ms 49872 KB Oczekiwano przedzialu o koszcie 461446 otrzymano przedzial wartosci 2
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 306 ms 49872 KB Oczekiwano przedzialu o koszcie 8939 otrzymano przedzial wartosci 2
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 729 ms 49872 KB Oczekiwano przedzialu o koszcie 54276 otrzymano przedzial wartosci 2
2 Halted 0 ms 0 KB -

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 663 ms 49872 KB Oczekiwano przedzialu o koszcie 1681121 otrzymano przedzial wartosci 2
2 Halted 0 ms 0 KB -