oj.uz

Submission #28948

# Submission time Handle Problem Language Result Execution time Memory
28948 2017-07-18T01:52:45 Z 시제연(#1229) Take-out (POI13_usu) C++11
88 / 100
 113 ms 65536 KB 
#include <bits/stdc++.h>

using namespace std;

int n, k, p;
char str[1000100];
int csum[1000100];
vector<int> cloc;
vector<int> res[1000100];

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[p].push_back(i);
		p++;
		return;
	}
	bool f1 = (getc(s,s+k)>0), f2 = (getc(e-k,e)>0);
	if (f1&&f2) {
		int idx = bs1(s,e);
		dnc(s,idx); dnc(idx+1,e);
	}
	else if (f1&&!f2) {
		int idx = (*lower_bound(cloc.begin(),cloc.end(),s));
		for (i=s;i<=idx;i++) res[p].push_back(i);
		for (i=e-k+idx-s+1;i<=e;i++) res[p].push_back(i);
		p++;
		dnc(idx+1,e-k+idx-s);
	}
	else if (!f1&&f2) {
		int idx = (*(--upper_bound(cloc.begin(),cloc.end(),e)));
		for (i=s;i<=s-e+k+idx-1;i++) res[p].push_back(i);
		for (i=idx;i<=e;i++) res[p].push_back(i);
		p++;
		dnc(s-e+k+idx,idx-1);
	}
	else {
		int idx = bs2(s,e);
		int r = (idx-s)%(k+1);
		for (i=s;i<s+r;i++) res[p].push_back(i);
		res[p].push_back(idx);
		for (i=e-k+r+1;i<=e;i++) res[p].push_back(i);
		p++;
		dnc(s+r,idx-1); dnc(idx+1,e-k+r);
	}
}

int main() {
	int i, j;

	scanf("%d%d",&n,&k);
	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<p;i++) {
		for (j=0;j<res[i].size();j++) printf("%d ",res[i][j]);
		printf("\n");
	}

    return 0;
}

Compilation message

usu.cpp: In function 'int main()':
usu.cpp:84:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (j=0;j<res[i].size();j++) printf("%d ",res[i][j]);
             ^
usu.cpp:76: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:77:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",str+1);
                   ^

Subtask #1
11.0 / 11.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 30344 KB Output is correct
2 Correct 9 ms 30476 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 31972 KB Output is correct
2 Correct 19 ms 31196 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 32308 KB Output is correct
2 Correct 39 ms 31828 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 33020 KB Output is correct
2 Correct 43 ms 31740 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 34704 KB Output is correct
2 Correct 109 ms 35060 KB Output is correct

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 76 ms 65536 KB Memory limit exceeded
2 Halted 0 ms 0 KB -