답안 #251473

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
251473	2020-07-21T10:46:25 Z	2qbingxuan	Lollipop (POI11_liz)	C++14	100 / 100	592 ms	31224 KB

#include <cstdio>
const int N = 1000025;
inline int max(int a, int b){return a>b ? a : b;}
inline int min(int a, int b){return a<b ? a : b;}
int n, q, v[N], sum[N];
int Z[N], lb[N*2];
char s[N];
signed main() {
  	scanf("%d%d%s", &n, &q, s);
    for(int i = 0; i < n; i++) v[i] = (s[i]=='T' ? 2 : 1);
    for(int i = 0; i < n; i++) sum[i+1] = sum[i] + v[i];
    for(int i = 1, j = 0; i <= n*2; i++) {
        while(j < n && sum[j] < i) ++j;
        lb[i] = j;
    }
    for(int i = 1, j = 0, r = 0; i < n; i++) {
        Z[i] = max(0, min(r-i, Z[i-j]));
        while(i+Z[i] < n && v[Z[i]] == v[i+Z[i]]) ++Z[i];
        if(i+Z[i] > r) j = i, r = i+Z[i];
    }
    Z[0] = n;
    while(q--) {
        int k;
      	scanf("%d", &k);
        int x = lb[k];
        if(sum[x] == k) printf("%d %d\n", 1, x);
        else {
            // sum[x] == k+1
            int L = Z[x]; // v[0:Z[x]-1] = v[x:x+Z[x]-1]
            // v[Z[x]] != v[x+Z[x]]
            int R = x+Z[x];
            /* debug(L, R); */
            if(v[L] == 1)
                --R;
            ++L;
            if(R >= n || sum[R+1] - sum[L] != k) puts("NIE");
            else printf("%d %d\n", L+1, R+1);
        }
    }
}

Compilation message

liz.cpp: In function 'int main()':
liz.cpp:9:9: 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:24:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
        scanf("%d", &k);
        ~~~~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

#	결과	메모리	Grader output
1	Correct	384 KB	Output is correct
2	Correct	384 KB	Output is correct
3	Correct	384 KB	Output is correct

Subtask #2
8.0 / 8.0

#	결과	메모리	Grader output
1	Correct	384 KB	Output is correct
2	Correct	384 KB	Output is correct
3	Correct	384 KB	Output is correct

Subtask #3
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	7 ms	512 KB	Output is correct

Subtask #4
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	512 KB	Output is correct
2	Correct	4 ms	512 KB	Output is correct
3	Correct	4 ms	640 KB	Output is correct

Subtask #5
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	896 KB	Output is correct
2	Correct	8 ms	896 KB	Output is correct
3	Correct	35 ms	1536 KB	Output is correct

Subtask #6
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	33 ms	2040 KB	Output is correct
2	Correct	144 ms	4472 KB	Output is correct
3	Correct	74 ms	3192 KB	Output is correct

Subtask #7
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	2296 KB	Output is correct
2	Correct	30 ms	2424 KB	Output is correct
3	Correct	72 ms	3960 KB	Output is correct

Subtask #8
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	119 ms	4884 KB	Output is correct
2	Correct	109 ms	4472 KB	Output is correct
3	Correct	149 ms	7416 KB	Output is correct

Subtask #9
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	278 ms	11960 KB	Output is correct
2	Correct	317 ms	11644 KB	Output is correct
3	Correct	331 ms	15736 KB	Output is correct

Subtask #10
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	277 ms	15120 KB	Output is correct
2	Correct	376 ms	16764 KB	Output is correct
3	Correct	437 ms	20344 KB	Output is correct

Subtask #11
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	589 ms	28920 KB	Output is correct
2	Correct	401 ms	27004 KB	Output is correct
3	Correct	586 ms	28280 KB	Output is correct

Subtask #12
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	592 ms	29824 KB	Output is correct
2	Correct	586 ms	29716 KB	Output is correct
3	Correct	417 ms	31224 KB	Output is correct