結果
問題 | No.504 ゲーム大会(ランキング) |
ユーザー | 紙ぺーぱー |
提出日時 | 2017-04-21 22:25:15 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 12,281 bytes |
コンパイル時間 | 3,763 ms |
コンパイル使用メモリ | 118,972 KB |
実行使用メモリ | 32,628 KB |
最終ジャッジ日時 | 2024-07-20 05:20:49 |
合計ジャッジ時間 | 7,376 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 26 ms
22,784 KB |
testcase_01 | AC | 26 ms
17,536 KB |
testcase_02 | AC | 27 ms
17,408 KB |
testcase_03 | AC | 26 ms
17,408 KB |
testcase_04 | AC | 26 ms
17,536 KB |
testcase_05 | AC | 27 ms
17,408 KB |
testcase_06 | AC | 26 ms
17,536 KB |
testcase_07 | AC | 299 ms
27,136 KB |
testcase_08 | AC | 286 ms
27,392 KB |
testcase_09 | AC | 293 ms
27,264 KB |
testcase_10 | AC | 293 ms
27,392 KB |
testcase_11 | AC | 297 ms
27,392 KB |
testcase_12 | TLE | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.Linq; using System.Collections.Generic; using Debug = System.Diagnostics.Debug; using StringBuilder = System.Text.StringBuilder; using Number = System.Int64; namespace Program { public class Solver { public void Solve() { var n = sc.Integer(); var a = sc.Long(n); var s = new Set<long>(); for (int i = 0; i < n; i++) { var x = a[i] * n + n - i; s.Add(x); Debug.WriteLine(s.AsJoinedString()); var p = s.LowerBound(a[0] * n + n); Debug.WriteLine(p); IO.Printer.Out.WriteLine(s.Count - p); } } public IO.StreamScanner sc = new IO.StreamScanner(Console.OpenStandardInput()); static T[] Enumerate<T>(int n, Func<int, T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; } static public void Swap<T>(ref T a, ref T b) { var tmp = a; a = b; b = tmp; } } } #region main static class Ex { static public string AsString(this IEnumerable<char> ie) { return new string(System.Linq.Enumerable.ToArray(ie)); } static public string AsJoinedString<T>(this IEnumerable<T> ie, string st = " ") { return string.Join(st, ie); } static public void Main() { var solver = new Program.Solver(); solver.Solve(); Program.IO.Printer.Out.Flush(); } } #endregion #region Ex namespace Program.IO { using System.IO; using System.Text; using System.Globalization; public class Printer: StreamWriter { static Printer() { Out = new Printer(Console.OpenStandardOutput()) { AutoFlush = false }; } public static Printer Out { get; set; } public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } } public Printer(System.IO.Stream stream) : base(stream, new UTF8Encoding(false, true)) { } public Printer(System.IO.Stream stream, Encoding encoding) : base(stream, encoding) { } public void Write<T>(string format, T[] source) { base.Write(format, source.OfType<object>().ToArray()); } public void WriteLine<T>(string format, T[] source) { base.WriteLine(format, source.OfType<object>().ToArray()); } } public class StreamScanner { public StreamScanner(Stream stream) { str = stream; } public readonly Stream str; private readonly byte[] buf = new byte[1024]; private int len, ptr; public bool isEof = false; public bool IsEndOfStream { get { return isEof; } } private byte read() { if (isEof) return 0; if (ptr >= len) { ptr = 0; if ((len = str.Read(buf, 0, 1024)) <= 0) { isEof = true; return 0; } } return buf[ptr++]; } public char Char() { byte b = 0; do b = read(); while ((b < 33 || 126 < b) && !isEof); return (char)b; } public string Scan() { var sb = new StringBuilder(); for (var b = Char(); b >= 33 && b <= 126; b = (char)read()) sb.Append(b); return sb.ToString(); } public string ScanLine() { var sb = new StringBuilder(); for (var b = Char(); b != '\n'; b = (char)read()) if (b == 0) break; else if (b != '\r') sb.Append(b); return sb.ToString(); } public long Long() { if (isEof) return long.MinValue; long ret = 0; byte b = 0; var ng = false; do b = read(); while (b != 0 && b != '-' && (b < '0' || '9' < b)); if (b == 0) return long.MinValue; if (b == '-') { ng = true; b = read(); } for (; true; b = read()) { if (b < '0' || '9' < b) return ng ? -ret : ret; else ret = ret * 10 + b - '0'; } } public int Integer() { return (isEof) ? int.MinValue : (int)Long(); } public double Double() { var s = Scan(); return s != "" ? double.Parse(s, CultureInfo.InvariantCulture) : double.NaN; } private T[] enumerate<T>(int n, Func<T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(); return a; } public char[] Char(int n) { return enumerate(n, Char); } public string[] Scan(int n) { return enumerate(n, Scan); } public double[] Double(int n) { return enumerate(n, Double); } public int[] Integer(int n) { return enumerate(n, Integer); } public long[] Long(int n) { return enumerate(n, Long); } } } #endregion #region Set public class Set<T>: ICollection<T> { public Set() { cmp = Comparer<T>.Default; } public Set(IComparer<T> comparer) { cmp = comparer; } public Set(Comparison<T> compare) { cmp = Comparer<T>.Create(compare); } AVLTree<Node> tree = new AVLTree<Node>(); IComparer<T> cmp; /// <summary> /// 値の重複を許すならばtrue,そうでなければfalse /// </summary> public bool IsMultiSet { get; set; } /// <summary> /// コレクションのサイズ. O(1) /// </summary> public int Count { get { return tree.Count; } } /// <summary> /// 要素の追加.成功した場合true,そうでなければfalse.O(logN) /// </summary> public bool Add(T item) { var v = new Node() { Key = item }; var lb = LowerBound(item); if (!IsMultiSet && UpperBound(item) != lb) return false; tree.Insert(v, lb); return true; } /// <summary> /// 要素の削除.成功した場合true,そうでなければfalse.O(logN) /// </summary> public bool Remove(T item) { var lb = LowerBound(item); var ub = UpperBound(item); if (ub == lb) return false; tree.RemoveAt(lb); return true; } /// <summary> /// 0-indexed で k 番目に小さい要素を削除.成功した場合true,そうでなければfalse.O(logN) /// </summary> public bool RemoveAt(int k) { if (k < 0 || k >= Count) return false; tree.RemoveAt(k); return true; } /// <summary> /// 0-indexed で k 番目に小さい要素を返す.O(logN) /// </summary> public T this[int index] { get { if (index < 0 || index >= Count) throw new IndexOutOfRangeException(); var t = tree.Find(tree.root, index); return t.Key; } } /// <summary> /// 要素があるなら true,そうでなければfalse /// </summary> public bool Contains(T item) { return UpperBound(item) != LowerBound(item); } /// <summary> /// itemの値以上の要素の最小のインデックスを返す.O(logN) /// </summary> public int LowerBound(T item) { return tree.LowerBound(tree.root, item, cmp); } /// <summary> /// itemの値より大きい要素の最小のインデックスを返す.O(logN) /// </summary> public int UpperBound(T item) { return tree.UpperBound(tree.root, item, cmp); } /// <summary> /// O(N)でなめる /// </summary> public T[] Items { get { var ret = new T[Count]; int ptr = 0; walk(tree.root, ret, ref ptr); return ret; } } public bool IsReadOnly { get { return false; } } void walk(Node root, T[] a, ref int ptr) { if (root == null) return; walk(root.lst, a, ref ptr); a[ptr++] = root.Key; walk(root.rst, a, ref ptr); } void ICollection<T>.Add(T item) { Add(item); } public void Clear() { tree.root = null; } public void CopyTo(T[] array, int arrayIndex) { ((ICollection<T>)Items).CopyTo(array, arrayIndex); } public IEnumerator<T> GetEnumerator() { return ((ICollection<T>)Items).GetEnumerator(); } System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return ((ICollection<T>)Items).GetEnumerator(); } class Node: AVLTreeNode<Node>, IKey<T> { public T Key { get; set; } public override Node Push() { return this; } } } #endregion #region AVLTree public abstract class AVLTreeNode<T>: BinaryTreeNode<T> where T : AVLTreeNode<T> { public int rank; public override void Update() { cnt = 1; if (lst != null) cnt += lst.cnt; if (rst != null) cnt += rst.cnt; } } public class AVLTree<T>: Tree<T> where T : AVLTreeNode<T> { int h(T t) { return t == null ? 0 : t.rank; } protected override T insert(T t, T v, int k) { t = push(t); if (t == null) { v.Update(); return v; } if (sz(t.lst) >= k) t.lst = insert(t.lst, v, k); else t.rst = insert(t.rst, v, k - sz(t.lst) - 1); t.Update(); return balance(t); } protected override T removeat(T t, int k) { t = push(t); var cnt = sz(t.lst); if (cnt < k) t.rst = removeat(t.rst, k - cnt - 1); else if (cnt > k) t.lst = removeat(t.lst, k); else { if (cnt == 0) return t.rst; if (sz(t.rst) == 0) return t.lst; var next = Find(t, k - 1); var st = removeat(t.lst, k - 1); next.rst = t.rst; next.lst = st; t = next; } t.Update(); return balance(t); } T balance(T t) { if (h(t.lst) - h(t.rst) == -2) { if (h(t.rst.lst) - h(t.rst.rst) > 0) t.rst = rotR(t.rst); t = rotL(t); } else if (h(t.lst) - h(t.rst) == 2) { if (h(t.lst.lst) - h(t.lst.rst) < 0) t.lst = rotL(t.lst); t = rotR(t); } t.Update(); return t; } } #endregion #region BinaryTree public interface IKey<K> { K Key { get; set; } } public abstract class BinaryTreeNode<T> where T : BinaryTreeNode<T> { public int cnt; public T lst, rst; public abstract T Push(); /// <summary> /// 各ノードは必要に応じて Update を継承して使う /// </summary> public abstract void Update(); } public abstract class Tree<TNode> where TNode : BinaryTreeNode<TNode> { public TNode root; public int Count { get { return sz(root); } } protected int sz(TNode t) { return t == null ? 0 : t.cnt; } protected TNode push(TNode t) { return t == null ? null : t.Push(); } protected TNode rotR(TNode t) { t = push(t); var l = push(t.lst); var lr = l.rst; l.rst = t; t.lst = lr; t.Update(); l.Update(); return l; } protected TNode rotL(TNode t) { t = push(t); var r = push(t.rst); var rl = r.lst; t.rst = rl; r.lst = t; t.Update(); r.Update(); return r; } public TNode Find(TNode t, int k) { t = push(t); if (k == sz(t.lst)) return t; else if (k < sz(t.lst)) return Find(t.lst, k); else return Find(t.rst, k - sz(t.lst) - 1); } public int LowerBound<T, K> (T t, K k, IComparer<K> cmp) where T : BinaryTreeNode<T>, IKey<K> { if (t == null) return 0; t = t.Push(); if (cmp.Compare(k, t.Key) <= 0) return LowerBound(t.lst, k, cmp); else return (t.lst == null ? 1 : (1 + t.lst.cnt)) + LowerBound(t.rst, k, cmp); } public int UpperBound<T, K> (T t, K k, IComparer<K> cmp) where T : BinaryTreeNode<T>, IKey<K> { if (t == null) return 0; t = t.Push(); if (cmp.Compare(t.Key, k) <= 0) return (t.lst == null ? 1 : (1 + t.lst.cnt)) + UpperBound(t.rst, k, cmp); else return UpperBound(t.lst, k, cmp); } public void Insert(TNode v, int k) { root = insert(root, v, k); } public void RemoveAt(int k) { root = removeat(root, k); } protected abstract TNode insert(TNode t, TNode v, int k); protected abstract TNode removeat(TNode t, int k); } #endregion