結果

問題 No.910 素数部分列
ユーザー claw88
提出日時 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.

ソースコード

diff #
プレゼンテーションモードにする

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)i19, 991, 11
if (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;
//1i使
int esti = A[i];
//get
int 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);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0