#390919 (C++14) No.910 素数部分列

• 問題: No.910 素数部分列
• ユーザー: QCFium
• 提出日時: 2019-10-18 21:50:49
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 969 bytes
• コンパイル時間: 1,539 ms
• コンパイル使用メモリ: 167,756 KB
• 実行使用メモリ: 4,688 KB
• 最終ジャッジ日時: 2023-09-07 21:56:10
• 合計ジャッジ時間: 3,689 ms
• ジャッジサーバーID （参考情報）: judge13 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,376 KB
testcase_01	AC	1 ms; 4,380 KB
testcase_02	AC	1 ms; 4,376 KB
testcase_03	AC	1 ms; 4,380 KB
testcase_04	AC	2 ms; 4,376 KB
testcase_05	AC	2 ms; 4,380 KB
testcase_06	AC	2 ms; 4,376 KB
testcase_07	WA	-
testcase_08	AC	2 ms; 4,380 KB
testcase_09	AC	2 ms; 4,380 KB
testcase_10	WA	-
testcase_11	AC	2 ms; 4,376 KB
testcase_12	AC	1 ms; 4,376 KB
testcase_13	AC	2 ms; 4,376 KB
testcase_14	AC	2 ms; 4,376 KB
testcase_15	WA	-
testcase_16	WA	-
testcase_17	AC	1 ms; 4,376 KB
testcase_18	WA	-
testcase_19	AC	2 ms; 4,376 KB
testcase_20	WA	-
testcase_21	WA	-
testcase_22	AC	2 ms; 4,376 KB
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-
testcase_35	WA	-
testcase_36	WA	-
testcase_37	WA	-
testcase_38	WA	-
testcase_39	AC	10 ms; 4,464 KB
testcase_40	AC	10 ms; 4,380 KB
testcase_41	AC	10 ms; 4,376 KB
testcase_42	AC	10 ms; 4,400 KB
testcase_43	AC	9 ms; 4,380 KB
testcase_44	AC	10 ms; 4,380 KB
testcase_45	AC	9 ms; 4,376 KB
testcase_46	AC	9 ms; 4,380 KB
testcase_47	AC	10 ms; 4,380 KB
testcase_48	AC	8 ms; 4,688 KB
testcase_49	AC	8 ms; 4,648 KB
testcase_50	AC	8 ms; 4,620 KB
testcase_51	AC	6 ms; 4,376 KB
testcase_52	AC	7 ms; 4,380 KB

ソースコード

#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

int main() {
	int n = ri();
	std::string s;
	std::cin >> s;
	int res = 0;
	std::string s_;
	for (int i = 0; i < n; i++) {
		if (s[i] == '3' || s[i] == '5' || s[i] == '7') res++;
		else s_.push_back(s[i]);
	}
	std::swap(s, s_);
	
	int l = 0;
	int r = (int) s.size() - 1;
	while (l < r) {
		while (l < (int) s.size() && s[l] != '1') l++;
		while (r >= 0 && s[r] != '9') r--;
		if (r <= l) break;
		s[l] = '0';
		s[r] = '0';
		l++, r--;
		res++;
	}
	s_.clear();
	std::vector<int> pos1, pos9;
	for (int i = 0; i < (int) s.size(); i++) {
		if (s[i] != '0') {
			s_.push_back(s[i]);
			if (s[i] == '9') pos9.push_back(i);
			else pos1.push_back(i);
		}
	}
	std::swap(s_, s);
	for (int i = (int) pos9.size() - 2; i >= 0; i--) {
		int pos = pos9[i + 1];
		if (pos1.size() && pos1.back() > pos) pos1.pop_back(), i--, res++;
	}
	res += pos1.size() / 2;
	std::cout << res << std::endl;
	
	
	return 0;
}