oj.uz

Submission #50686

# Submission time Handle Problem Language Result Execution time Memory
50686 2018-06-12T15:21:31 Z szawinis Lollipop (POI11_liz) C++17
100 / 100
 719 ms 123896 KB 
#include <bits/stdc++.h>
using namespace std;
#define fori(i, a, b) for(int i = (int) a; i <= (int) b; ++i)
#define rofi(i, b, a) for(int i = (int) b; i >= (int) a; --i)
#define foreach(tt, a) for(auto &tt: a)
#define all(a) begin(a), end(a)
#define csz(a) (int) a.size()
#define pb push_back
#define epb emplace_back
#define mp make_pair
#define load(a, v) fill(begin(a), end(a), v)
#define load_mem(a, v) memset(a, v, sizeof(a));
#define iostream_optimize() ios::sync_with_stdio(false); cin.tie(0);
using ll = long long;
const ll MOD = 1e9+7, LINF = 1e16+1;
const int INF = 1e9+1;
const double EPS = 1e-10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
const ll P1 = 31, P2 = 37, M1 = 1e9+7, M2 = 1e9+9;

// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// template <typename T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
/* <<<<<<<<<<<<<<<<<<<<<<<<<<<< END TEMPLATE >>>>>>>>>>>>>>>>>>>>>>>>>>> */
const int N = 1e6+2;

int n, q, a[N], sum[N], rev[2*N], nxt[N];
char s[N];

bool valid(int l, int r, int k) {
	return l <= r && l >= 1 && l <= n && r >= 1 && r <= n && (sum[r] - sum[l-1] == k);
}

int main() {
	scanf("%d %d %s", &n, &q, s);
	load_mem(rev, -1);
	load(nxt, INF);
	fori(i, 1, n) {
		a[i] = (s[i-1] == 'T' ? 2 : 1);
		sum[i] = sum[i-1] + a[i];
		rev[sum[i]] = i;
	}
	rofi(i, n, 2) {
		if(a[i] != a[i-1]) nxt[i-1] = i;
		else nxt[i-1] = nxt[i];
	}
	fori(z, 0, q-1) {
		int k; scanf("%d", &k);
		if(k > sum[n]) { printf("NIE\n"); continue; }
		if(rev[k] != -1) { printf("1 %d\n", rev[k]); continue; }

		int i = rev[k+1];
		int l = -1, r = -1;
		if(i == 1) {
			if(valid(nxt[i], nxt[i], k)) l = r = nxt[i];
		} else if(a[1] == 2 && a[i] == 2) {
			if(nxt[i] - i == nxt[1] - 1) {
				if(valid(nxt[1], nxt[i], k)) l = nxt[1], r = nxt[i];
			} else if(nxt[i] - i < nxt[1] - 1) {
				if(valid(nxt[i] - i + 1, nxt[i], k)) l = nxt[i] - i + 1, r = nxt[i];
			} else {
				if(valid(nxt[1] + 1, nxt[1] + i - 1, k)) l = nxt[1] + 1, r = nxt[1] + i - 1;
			}
		} else {
			if(a[1] == 1) l = 2, r = i;
			else if(a[i] == 1) l = 1, r = i-1;
			else assert(false);
		}
		if(l == -1 && r == -1) printf("NIE\n");
		else printf("%d %d\n", l, r);
	}
}

Compilation message

liz.cpp: In function 'int main()':
liz.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %s", &n, &q, s);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
liz.cpp:50:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int k; scanf("%d", &k);
          ~~~~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12000 KB Output is correct
2 Correct 10 ms 12136 KB Output is correct
3 Correct 11 ms 12136 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12180 KB Output is correct
2 Correct 10 ms 12180 KB Output is correct
3 Correct 10 ms 12180 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12188 KB Output is correct
2 Correct 12 ms 12320 KB Output is correct
3 Correct 16 ms 12452 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12564 KB Output is correct
2 Correct 14 ms 12752 KB Output is correct
3 Correct 15 ms 12928 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 13184 KB Output is correct
2 Correct 29 ms 13320 KB Output is correct
3 Correct 52 ms 14612 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 15176 KB Output is correct
2 Correct 185 ms 19968 KB Output is correct
3 Correct 85 ms 19968 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 19968 KB Output is correct
2 Correct 41 ms 20024 KB Output is correct
3 Correct 133 ms 22732 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 25432 KB Output is correct
2 Correct 114 ms 27020 KB Output is correct
3 Correct 194 ms 31948 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 39096 KB Output is correct
2 Correct 377 ms 42872 KB Output is correct
3 Correct 451 ms 50872 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 357 ms 53084 KB Output is correct
2 Correct 394 ms 59784 KB Output is correct
3 Correct 510 ms 68272 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 711 ms 81360 KB Output is correct
2 Correct 481 ms 88224 KB Output is correct
3 Correct 674 ms 97472 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 719 ms 106040 KB Output is correct
2 Correct 512 ms 114120 KB Output is correct
3 Correct 469 ms 123896 KB Output is correct