답안 #28958

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
28958 2017-07-18T02:01:34 Z tlwpdus Take-out (POI13_usu) C++11
100 / 100
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);
                   ^
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 6908 KB Output is correct
2 Correct 0 ms 6908 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 6908 KB Output is correct
2 Correct 0 ms 6908 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 6908 KB Output is correct
2 Correct 0 ms 6908 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8036 KB Output is correct
2 Correct 9 ms 7300 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 8268 KB Output is correct
2 Correct 36 ms 7972 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 8912 KB Output is correct
2 Correct 36 ms 8080 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 9876 KB Output is correct
2 Correct 76 ms 10036 KB Output is correct
# 결과 실행 시간 메모리 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