結果
問題 | No.910 素数部分列 |
ユーザー |
|
提出日時 | 2019-10-18 22:27:54 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 70 ms / 1,000 ms |
コード長 | 10,958 bytes |
コンパイル時間 | 1,342 ms |
コンパイル使用メモリ | 111,872 KB |
実行使用メモリ | 22,016 KB |
最終ジャッジ日時 | 2024-06-25 21:48:28 |
合計ジャッジ時間 | 5,704 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;using System.Collections.Generic;using System.Linq;using System.IO;using SB = System.Text.StringBuilder;//using System.Threading.Tasks;//using System.Text.RegularExpressions;//using System.Globalization;//using System.Diagnostics;using static System.Console;using System.Numerics;using static System.Math;using pair = Pair<int, int>;class Program{static void Main(){//SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });new Program().solve();Out.Flush();}readonly Scanner cin = new Scanner();readonly int[] dd = { 0, 1, 0, -1, 0 }; //→↓←↑readonly int mod = 1000000007;readonly int dom = 998244353;bool chmax<T>(ref T a, T b) where T : IComparable<T> { if (a.CompareTo(b) < 0) { a = b; return true; } return false; }bool chmin<T>(ref T a, T b) where T : IComparable<T> { if (b.CompareTo(a) < 0) { a = b; return true; } return false; }void solve(){int N = cin.nextint;var S = ReadLine();var one = new List<int>();//var ONE = new Set<int>();//var NIN = new Set<int>();var nin = new List<int>();int ans = 0;for (int i = 0; i < N; i++){if (S[i] == '3' || S[i] == '7' || S[i] == '5'){ans++;}else if (S[i] == '1'){one.Add(i);//ONE.Add(i);}else{nin.Add(i);//NIN.Add(i);}}var Z = new List<int>();for (int i = 1; i < nin.Count; i += 2){Z.Add(nin[i]);}var A = new int[one.Count + 1];int last = nin.Count;for (int i = one.Count - 1; i >= 0; i--){A[i] = A[i + 1];//one[i]より初めて小さくなるやつint idx = Z.lower_bound(one[i]) - 1;last = Min(last - 1, idx);if (last >= 0){A[i]++;}}int tmp = 0;int next = -1;for (int i = 0; i <= one.Count; i++){//[0,i)のi個を19, できるだけ991, のこりを11if (i > 0){int id = nin.upper_bound(one[i - 1]);next = Max(next + 1, id);if (next == nin.Count) break;}//残った9の数int R = nin.Count - i;if (R < 0) break;//1はiから使えるint esti = A[i];//getint get = Min(A[i], R / 2);//残った1の数int O = one.Count - i - get;get += O / 2;chmax(ref tmp, i + get);//WriteLine(i + get + " " + i);}WriteLine(ans + tmp);}}/// <OriginalAuthor>camypaper</OriginalAuthor>class Set<T>{Node root;readonly IComparer<T> comparer;readonly Node nil;readonly T nil_key;public bool IsMultiSet { get; set; }public Set(IComparer<T> comparer, T nil_key){this.nil_key = nil_key;nil = new Node(nil_key);root = nil;this.comparer = comparer;}public Set(Comparison<T> comaprison, T nil_key = default(T)) : this(Comparer<T>.Create(comaprison), nil_key) { }public Set(T nil_key = default(T)) : this(Comparer<T>.Default, nil_key) { }public bool Add(T v){key = v;return insert(ref root);}public bool Remove(T v){key = v;return remove(ref root);}public T this[int index] { get { return find(root, index); } }public int Count { get { return root.Count; } }public void RemoveAt(int k){if (k < 0 || k >= root.Count) throw new ArgumentOutOfRangeException();removeAt(ref root, k);}public T[] Items{get{var ret = new T[root.Count];var k = 0;walk(root, ret, ref k);return ret;}}void walk(Node t, T[] a, ref int k){if (t.Count == 0) return;walk(t.lst, a, ref k);a[k++] = t.Key;walk(t.rst, a, ref k);}T key;bool insert(ref Node t){if (t.Count == 0) { t = new Node(key); t.lst = t.rst = nil; t.Update(); return true; }var cmp = comparer.Compare(t.Key, key);bool res;if (cmp > 0)res = insert(ref t.lst);else if (cmp == 0){if (IsMultiSet) res = insert(ref t.lst);else return false;}else res = insert(ref t.rst);balance(ref t);return res;}bool remove(ref Node t){if (t.Count == 0) return false;var cmp = comparer.Compare(key, t.Key);bool ret;if (cmp < 0) ret = remove(ref t.lst);else if (cmp > 0) ret = remove(ref t.rst);else{ret = true;var k = t.lst.Count;if (k == 0) { t = t.rst; return true; }if (t.rst.Count == 0) { t = t.lst; return true; }t.Key = find(t.lst, k - 1);removeAt(ref t.lst, k - 1);}balance(ref t);return ret;}void removeAt(ref Node t, int k){var cnt = t.lst.Count;if (cnt < k) removeAt(ref t.rst, k - cnt - 1);else if (cnt > k) removeAt(ref t.lst, k);else{if (cnt == 0) { t = t.rst; return; }if (t.rst.Count == 0) { t = t.lst; return; }t.Key = find(t.lst, k - 1);removeAt(ref t.lst, k - 1);}balance(ref t);}void balance(ref Node t){var balance = t.lst.Height - t.rst.Height;if (balance == -2){if (t.rst.lst.Height - t.rst.rst.Height > 0) { rotR(ref t.rst); }rotL(ref t);}else if (balance == 2){if (t.lst.lst.Height - t.lst.rst.Height < 0) rotL(ref t.lst);rotR(ref t);}else t.Update();}T find(Node t, int k){if (k < 0 || k > root.Count) throw new ArgumentOutOfRangeException();for (; ; ){if (k == t.lst.Count) return t.Key;else if (k < t.lst.Count) t = t.lst;else { k -= t.lst.Count + 1; t = t.rst; }}}public int LowerBound(T v){var k = 0;var t = root;for (; ; ){if (t.Count == 0) return k;if (comparer.Compare(v, t.Key) <= 0) t = t.lst;else { k += t.lst.Count + 1; t = t.rst; }}}public int UpperBound(T v){var k = 0;var t = root;for (; ; ){if (t.Count == 0) return k;if (comparer.Compare(t.Key, v) <= 0) { k += t.lst.Count + 1; t = t.rst; }else t = t.lst;}}public T LowerBoundValue(T v){var t = root;T ret = nil_key;for (; ; ){if (t.Count == 0) return ret;if (comparer.Compare(v, t.Key) <= 0){ret = t.Key;t = t.lst;}else{t = t.rst;}}}public T UpperBoundValue(T v){var t = root;T ret = nil_key;for (; ; ){if (t.Count == 0) return ret;if (comparer.Compare(t.Key, v) <= 0){t = t.rst;}else{ret = t.Key;t = t.lst;}}}void rotR(ref Node t){var l = t.lst;t.lst = l.rst;l.rst = t;t.Update();l.Update();t = l;}void rotL(ref Node t){var r = t.rst;t.rst = r.lst;r.lst = t;t.Update();r.Update();t = r;}class Node{public Node(T key){Key = key;}public int Count { get; private set; }public sbyte Height { get; private set; }public T Key { get; set; }public Node lst, rst;public void Update(){Count = 1 + lst.Count + rst.Count;Height = (sbyte)(1 + Math.Max(lst.Height, rst.Height));}public override string ToString(){return string.Format("Count = {0}, Key = {1}", Count, Key);}}}static class Ex{public static void join<T>(this IEnumerable<T> values, string sep = " ") => WriteLine(string.Join(sep, values));public static string concat<T>(this IEnumerable<T> values) => string.Concat(values);public static string reverse(this string s) { var t = s.ToCharArray(); Array.Reverse(t); return t.concat(); }public static int lower_bound<T>(this IList<T> arr, T val) where T : IComparable<T>{int low = 0, high = arr.Count;int mid;while (low < high){mid = ((high - low) >> 1) + low;if (arr[mid].CompareTo(val) < 0) low = mid + 1;else high = mid;}return low;}public static int upper_bound<T>(this IList<T> arr, T val) where T : IComparable<T>{int low = 0, high = arr.Count;int mid;while (low < high){mid = ((high - low) >> 1) + low;if (arr[mid].CompareTo(val) <= 0) low = mid + 1;else high = mid;}return low;}}class Pair<T, U> : IComparable<Pair<T, U>> where T : IComparable<T> where U : IComparable<U>{public T f; public U s;public Pair(T f, U s) { this.f = f; this.s = s; }public int CompareTo(Pair<T, U> a) => f.CompareTo(a.f) != 0 ? f.CompareTo(a.f) : s.CompareTo(a.s);public override string ToString() => $"{f} {s}";}class Scanner{string[] s; int i;readonly char[] cs = new char[] { ' ' };public Scanner() { s = new string[0]; i = 0; }public string[] scan => ReadLine().Split();public int[] scanint => Array.ConvertAll(scan, int.Parse);public long[] scanlong => Array.ConvertAll(scan, long.Parse);public double[] scandouble => Array.ConvertAll(scan, double.Parse);public string next{get{if (i < s.Length) return s[i++];string st = ReadLine();while (st == "") st = ReadLine();s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);i = 0;return next;}}public int nextint => int.Parse(next);public long nextlong => long.Parse(next);public double nextdouble => double.Parse(next);}