Beta Round #64-B: Text Messaging

解法

実装するだけ。スペースを消去できるのはmessage間だけ(text間ではない)ことに気づかなかったけどcodeforcesにしては珍しくpretestで弾いてくれた。

#include <cstdio>
#include <algorithm>
#include <vector>
#include <string.h>
#include <iostream>
using namespace std;

char str[100009];
int N;

int solve(){
	vector<int> ns, ws, ls;
	//ns.push_back(-1);
	for(int i=0; i<strlen(str); i++){
		if(str[i] == '.' || str[i] == '?' || str[i] == '!'){
			ns.push_back(i);
		}
		if(str[i] != ' '){
			ws.push_back(i);
		}
	}
	for(int i=0; i<ns.size(); i++){
		int u = i>0?*upper_bound(ws.begin(), ws.end(), ns[i-1]):ws[0];
		int v = *lower_bound(ws.begin(), ws.end(), ns[i]);
		if(v - u + 1 > N) return -1;
	}
	int ans = 1, cur = 0, pre=ws[0];
	for(int i=0; i<ns.size(); i++){
		int post = *lower_bound(ws.begin(), ws.end(), ns[i]);
		if(post - pre + 1<= N){
			cur = post - pre + 1;
		}
		else{
			ans++;
			pre = *upper_bound(ws.begin(), ws.end(), ns[i-1]);
		}
	}
	return ans;
}

int main(){
	scanf("%d ",&N);
	gets(str);
	int ans = solve();
	if(ans<0){
		puts("Impossible");
	}
	else{
		printf("%d\n",ans);
	}
	return 0;
}