oj.uz

Submission #29747

# Submission time Handle Problem Language Result Execution time Memory
29747 2017-07-20T13:19:49 Z cki86201 Lollipop (POI11_liz) C++11
100 / 100
 1176 ms 14716 KB 
#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

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.0 / 8.0

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

Subtask #2
8.0 / 8.0

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

Subtask #3
8.0 / 8.0

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

Subtask #4
8.0 / 8.0

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

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14716 KB Output is correct
2 Correct 9 ms 14716 KB Output is correct
3 Correct 66 ms 14716 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 14716 KB Output is correct
2 Correct 243 ms 14716 KB Output is correct
3 Correct 136 ms 14716 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 14716 KB Output is correct
2 Correct 46 ms 14716 KB Output is correct
3 Correct 159 ms 14716 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 14716 KB Output is correct
2 Correct 193 ms 14716 KB Output is correct
3 Correct 423 ms 14716 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 14716 KB Output is correct
2 Correct 376 ms 14716 KB Output is correct
3 Correct 753 ms 14716 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 14716 KB Output is correct
2 Correct 509 ms 14716 KB Output is correct
3 Correct 893 ms 14716 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 943 ms 14716 KB Output is correct
2 Correct 833 ms 14716 KB Output is correct
3 Correct 1176 ms 14716 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 756 ms 14716 KB Output is correct
2 Correct 913 ms 14716 KB Output is correct
3 Correct 773 ms 14716 KB Output is correct