oj.uz

Submission #29527

# Submission time Handle Problem Language Result Execution time Memory
29527 2017-07-20T05:12:26 Z 윤교준(#1243) Lollipop (POI11_liz) C++11
100 / 100
 699 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]]) {
			/*for(int j = 1; j <= EX[Q[i]]; j++) {
				int sum = S[EX[Q[i]]] - S[j-1];
				if(sum == Q[i]) {
					Ans[i] = {j+widx-1, EX[Q[i]]+widx-1};
					break;
				}
			} */
			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) printf("-1 -1\n");
		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:87: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:88: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
8.0 / 8.0

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

Subtask #2
8.0 / 8.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 49872 KB Output is correct
2 Correct 9 ms 49872 KB Output is correct
3 Correct 19 ms 49872 KB Output is correct

Subtask #4
8.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 Correct 9 ms 49872 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 49872 KB Output is correct
2 Correct 13 ms 49872 KB Output is correct
3 Correct 39 ms 49872 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 49872 KB Output is correct
2 Correct 166 ms 49872 KB Output is correct
3 Correct 103 ms 49872 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 49872 KB Output is correct
2 Correct 29 ms 49872 KB Output is correct
3 Correct 89 ms 49872 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 49872 KB Output is correct
2 Correct 133 ms 49872 KB Output is correct
3 Correct 189 ms 49872 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 49872 KB Output is correct
2 Correct 309 ms 49872 KB Output is correct
3 Correct 356 ms 49872 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 49872 KB Output is correct
2 Correct 296 ms 49872 KB Output is correct
3 Correct 403 ms 49872 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 466 ms 49872 KB Output is correct
2 Correct 609 ms 49872 KB Output is correct
3 Correct 576 ms 49872 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 699 ms 49872 KB Output is correct
2 Correct 699 ms 49872 KB Output is correct
3 Correct 423 ms 49872 KB Output is correct