結果
問題 | No.910 素数部分列 |
ユーザー | claw88 |
提出日時 | 2019-10-18 22:10:10 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 10,714 bytes |
コンパイル時間 | 1,198 ms |
コンパイル使用メモリ | 118,496 KB |
実行使用メモリ | 28,772 KB |
最終ジャッジ日時 | 2024-06-25 17:04:38 |
合計ジャッジ時間 | 5,149 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 27 ms
26,052 KB |
testcase_01 | AC | 28 ms
24,040 KB |
testcase_02 | AC | 28 ms
23,528 KB |
testcase_03 | AC | 28 ms
24,012 KB |
testcase_04 | AC | 28 ms
23,908 KB |
testcase_05 | AC | 28 ms
24,168 KB |
testcase_06 | AC | 28 ms
25,916 KB |
testcase_07 | AC | 28 ms
24,264 KB |
testcase_08 | AC | 29 ms
23,784 KB |
testcase_09 | AC | 29 ms
26,080 KB |
testcase_10 | AC | 29 ms
26,052 KB |
testcase_11 | AC | 28 ms
26,040 KB |
testcase_12 | AC | 28 ms
26,052 KB |
testcase_13 | AC | 28 ms
23,788 KB |
testcase_14 | AC | 27 ms
23,872 KB |
testcase_15 | WA | - |
testcase_16 | AC | 28 ms
23,724 KB |
testcase_17 | AC | 27 ms
24,040 KB |
testcase_18 | AC | 28 ms
25,948 KB |
testcase_19 | AC | 27 ms
23,604 KB |
testcase_20 | WA | - |
testcase_21 | AC | 28 ms
24,040 KB |
testcase_22 | AC | 27 ms
25,664 KB |
testcase_23 | AC | 48 ms
25,192 KB |
testcase_24 | AC | 49 ms
27,408 KB |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | AC | 49 ms
27,260 KB |
testcase_28 | AC | 50 ms
25,116 KB |
testcase_29 | WA | - |
testcase_30 | AC | 75 ms
28,640 KB |
testcase_31 | AC | 73 ms
24,380 KB |
testcase_32 | AC | 76 ms
28,204 KB |
testcase_33 | WA | - |
testcase_34 | WA | - |
testcase_35 | WA | - |
testcase_36 | WA | - |
testcase_37 | WA | - |
testcase_38 | WA | - |
testcase_39 | WA | - |
testcase_40 | WA | - |
testcase_41 | AC | 70 ms
26,420 KB |
testcase_42 | WA | - |
testcase_43 | AC | 69 ms
27,368 KB |
testcase_44 | AC | 68 ms
26,728 KB |
testcase_45 | AC | 70 ms
26,472 KB |
testcase_46 | AC | 70 ms
28,464 KB |
testcase_47 | AC | 72 ms
26,420 KB |
testcase_48 | AC | 34 ms
28,040 KB |
testcase_49 | AC | 33 ms
25,776 KB |
testcase_50 | AC | 33 ms
23,856 KB |
testcase_51 | AC | 30 ms
26,084 KB |
testcase_52 | AC | 49 ms
26,028 KB |
コンパイルメッセージ
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) { int idx = one.upper_bound(nin[i]); if (idx == one.Count) break; Z.Add(idx); } int tmp = 0; int last = -1; for (int i = 0; i <= one.Count; i++) { //[0,i)のi個を19, できるだけ991, のこりを11 if (i > 0) { int id = nin.upper_bound(one[i - 1]); chmax(ref id, last + 1); if (id == nin.Count) break; last = id; } //残った9の数 int R = nin.Count - i; if (R < 0) break; //1はiから使える int idx = Z.lower_bound(i); //get int get = Min(Z.Count - idx, Min(R / 2, one.Count - i)); //残った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); }