Submission #29747

#	Time	Username	Problem	Language	Result	Execution time	Memory
29747		cki86201	Lollipop (POI11_liz)	C++11	100 / 100	1176 ms	14716 KiB

liz

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>
 
using namespace std;
typedef pair<int, int> Pi;
typedef long long ll;
#define pii Pi
#define pll PL
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> PL;
typedef long double ldouble;
 
int n, m;
char A[1000010];
int S[1000010];
int nxt[1000010], pre[1000010];
 
int main(){
	scanf("%d%d", &n, &m);
	scanf("%s", A+1);
	for(int i=1;i<=n;i++) S[i] = S[i-1] + (A[i] == 'T' ? 2 : 1);
	pre[0] = -1, nxt[n + 1] = -1;
	for(int i=1;i<=n;i++) pre[i] = (A[i] == 'T' ? pre[i-1] : i);
	for(int i=n;i;i--) nxt[i] = (A[i] == 'T' ? nxt[i+1] : i);
	rep(i, m) {
		int x; scanf("%d", &x);
		if(x > S[n]) puts("NIE");
		else {
			int a = (int)(upper_bound(S, S+1+n, x) - S - 1);
			if(S[a] == x) printf("%d %d\n", 1, a);
			else {
				int b = (int)(lower_bound(S, S+1+n, S[n] - x) - S);
				if(S[b] == S[n] - x) printf("%d %d\n", b+1, n);
				else {
					int t = nxt[a+1], t2 = pre[b];
					if(t != -1) {
						int c = (int)(lower_bound(S, S+1+n, S[t-1] - x) - S);
						if(S[c] == S[t-1] - x) printf("%d %d\n", c+1, t-1);
						else printf("%d %d\n", c+1, t);
					}
					else if(t2 != -1) {
						int c = (int)(upper_bound(S, S+1+n, S[t2] + x) - S - 1);
						if(S[c] == S[t2] + x) printf("%d %d\n", t2+1, c);
						else printf("%d %d\n", t2, c);
					}
					else puts("NIE");
				}
			}
		}
	}
	return 0;
}

Compilation message (stderr)

liz.cpp: In function 'int main()':
liz.cpp:40:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
                       ^
liz.cpp:41:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", A+1);
                  ^
liz.cpp:47:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x; scanf("%d", &x);
                         ^

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 8 / 8
• Subtask 5: 8 / 8
• Subtask 6: 8 / 8
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9
• Subtask 12: 9 / 9