Submission #28958

#	Time	Username	Problem	Language	Result	Execution time	Memory
28958		tlwpdus	Take-out (POI13_usu)	C++11	100 / 100	163 ms	43896 KiB

usu

#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 (stderr)

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);
                   ^

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 11 / 11
• Subtask 9: 12 / 12