| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 28958 |
2017-07-18T02:01:34 Z |
tlwpdus |
Take-out (POI13_usu) |
C++11 |
|
163 ms |
43896 KB |
#include <bits/stdc++.h>
using namespace std;
int n, k;
char str[1000100];
int csum[1000100];
vector<int> cloc;
vector<int> res;
int getc(int s, int e) {
return csum[e]-csum[s-1];
}
int bs1(int a, int b) {
int s = 1, e = (b-a+1)/(k+1)-1;
while(s<=e) {
int m = (s+e)>>1;
if (getc(a,a+(k+1)*m-1)==m) return a+(k+1)*m-1;
else if (getc(a,a+(k+1)*m-1)>m) s = m+1;
else e = m-1;
}
return a+(k-1)*s-1;
}
int bs2(int a, int b) {
int s = a, e = b;
while(s<=e) {
int m = (s+e)>>1;
if (getc(a,m)>=(m-a)/(k+1)+1) e = m-1;
else s = m+1;
}
return s;
}
void dnc(int s, int e) {
int i;
if (s+k==e) {
for (i=s;i<=e;i++) res.push_back(i);
return;
}
if (getc(s,s+k)>0&&getc(e-k,e)>0) {
int idx = bs1(s,e);
dnc(s,idx); dnc(idx+1,e);
}
else if (getc(s,s+k)>0&&getc(e-k,e)<=0) {
int idx = (*lower_bound(cloc.begin(),cloc.end(),s));
for (i=s;i<=idx;i++) res.push_back(i);
for (i=e-k+idx-s+1;i<=e;i++) res.push_back(i);
dnc(idx+1,e-k+idx-s);
}
else if (getc(s,s+k)<=0&&getc(e-k,e)>0) {
int idx = (*(--upper_bound(cloc.begin(),cloc.end(),e)));
for (i=s;i<=s-e+k+idx-1;i++) res.push_back(i);
for (i=idx;i<=e;i++) res.push_back(i);
dnc(s-e+k+idx,idx-1);
}
else {
int idx = bs2(s,e);
for (i=s;i<s+(idx-s)%(k+1);i++) res.push_back(i);
res.push_back(idx);
for (i=e-k+(idx-s)%(k+1)+1;i<=e;i++) res.push_back(i);
dnc(s+(idx-s)%(k+1),idx-1); dnc(idx+1,e-k+(idx-s)%(k+1));
}
}
int main() {
int i, j;
scanf("%d%d",&n,&k);
cloc.reserve(n/(k+1)+10);
res.reserve(n+10);
scanf("%s",str+1);
for (i=1;i<=n;i++) {
csum[i] = csum[i-1]+(str[i]=='c');
if (str[i]=='c') cloc.push_back(i);
}
dnc(1,n);
for (i=0;i<n/(k+1);i++) {
for (j=i*(k+1);j<(i+1)*(k+1);j++) printf("%d ",res[j]);
printf("\n");
}
return 0;
}
Compilation message
usu.cpp: In function 'int main()':
usu.cpp:70:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&k);
^
usu.cpp:73:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",str+1);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
6908 KB |
Output is correct |
| 2 |
Correct |
0 ms |
6908 KB |
Output is correct |
| 3 |
Correct |
0 ms |
6908 KB |
Output is correct |
| 4 |
Correct |
0 ms |
6908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
6908 KB |
Output is correct |
| 2 |
Correct |
0 ms |
6908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
6908 KB |
Output is correct |
| 2 |
Correct |
0 ms |
6908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
6908 KB |
Output is correct |
| 2 |
Correct |
0 ms |
6908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
8036 KB |
Output is correct |
| 2 |
Correct |
9 ms |
7300 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
8268 KB |
Output is correct |
| 2 |
Correct |
36 ms |
7972 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
8912 KB |
Output is correct |
| 2 |
Correct |
36 ms |
8080 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
9876 KB |
Output is correct |
| 2 |
Correct |
76 ms |
10036 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
163 ms |
43896 KB |
Output is correct |
| 2 |
Correct |
96 ms |
10816 KB |
Output is correct |
| 3 |
Correct |
99 ms |
10816 KB |
Output is correct |
| 4 |
Correct |
119 ms |
10932 KB |
Output is correct |
