Submission #874184


Source Code Expand

Copy
using System;
using System.Linq;
using System.Linq.Expressions;
using System.Collections.Generic;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
using System.Numerics;
using Number = System.Int64;
namespace Program
{
    public class Solver
    {
        public void Solve()
        {
            var n = sc.Integer();
            var m = sc.Integer();
            var G = Enumerate(n, x => new List<int>());
            var sw = new System.Diagnostics.Stopwatch();
            var rand = new Random();

            for (int i = 0; i < m; i++)
            {
                var x = sc.Integer() - 1;
                var y = sc.Integer() - 1;
                G[x].Add(y);
                G[y].Add(x);
            }
            var C = new int[n];
            while (sw.ElapsedMilliseconds < 1800)
            {
                for (int i = 0; i < n; i++)
                    C[i] = rand.Next() % 4 + 1;
                for (int k = 0; k < 50; k++)
                {
                    var id = rand.Next() % n;
                    var x = rand.Next() % 4 + 1;
                    C[id] = x;
                    var ok = true;
                    for (int i = 0; i < n && ok; i++)
                    {
                        foreach (var to in G[i])
                        {
                            if (C[i] == C[to]) { ok = false; break; }
                        }
                    }
                    if (ok)
                    {
                        foreach (var v in C)
                            IO.Printer.Out.WriteLine(v);
                        return;
                    }
                }

            }
        }

        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

Submission Info

Submission Time
Task B - 今年の B 問題
User camypaper
Language C# (Mono 4.6.2.0)
Score 240
Code Size 5848 Byte
Status TLE
Exec Time 2106 ms
Memory 2900 KB

Judge Result

Set Name All camypaper DEGwer dnk E869120 ei1333 Huziwara IH19980412 japlj joisino maroonrk rickytheta satashun satos semiexp sigma425 sugim48 tozangezan wo01 yosupo
Score / Max Score 200 / 200 10 / 10 0 / 10 0 / 10 0 / 10 0 / 10 0 / 10 0 / 10 10 / 10 0 / 10 0 / 10 0 / 10 0 / 10 0 / 10 0 / 10 10 / 10 0 / 10 0 / 10 0 / 10 10 / 10
Status
AC × 18
AC × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 1
AC × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 1
AC × 1
TLE × 1
TLE × 1
TLE × 1
AC × 1
Set Name Test Cases
All 00_sample_00, 00_sample_01, 10_manual_01, 10_manual_02, 10_manual_03, 10_manual_04, 10_manual_05, 10_manual_06, 10_manual_07, 10_manual_08, 10_manual_09, 10_manual_10, 10_manual_11, 10_manual_12, 10_manual_13, 10_manual_14, 10_manual_15, 10_manual_16
camypaper 30_camypaper
DEGwer 30_DEGwer
dnk 30_dnk
E869120 30_E869120
ei1333 30_ei1333
Huziwara 30_Huziwara
IH19980412 30_IH19980412
japlj 30_japlj
joisino 30_joisino
maroonrk 30_maroonrk
rickytheta 30_rickytheta
satashun 30_satashun
satos 30_satos
semiexp 30_semiexp
sigma425 30_sigma425
sugim48 30_sugim48
tozangezan 30_tozangezan
wo01 30_wo01
yosupo 30_yosupo
Case Name Status Exec Time Memory
00_sample_00 AC 37 ms 2900 KB
00_sample_01 AC 34 ms 2772 KB
10_manual_01 AC 35 ms 2772 KB
10_manual_02 AC 35 ms 2772 KB
10_manual_03 AC 34 ms 2772 KB
10_manual_04 AC 35 ms 2772 KB
10_manual_05 AC 35 ms 2772 KB
10_manual_06 AC 35 ms 2772 KB
10_manual_07 AC 34 ms 2772 KB
10_manual_08 AC 34 ms 2772 KB
10_manual_09 AC 34 ms 2772 KB
10_manual_10 AC 34 ms 2772 KB
10_manual_11 AC 34 ms 2772 KB
10_manual_12 AC 34 ms 2772 KB
10_manual_13 AC 34 ms 2772 KB
10_manual_14 AC 34 ms 2772 KB
10_manual_15 AC 34 ms 2772 KB
10_manual_16 AC 34 ms 2772 KB
30_DEGwer TLE 2102 ms 2524 KB
30_E869120 TLE 2102 ms 2400 KB
30_Huziwara TLE 2105 ms 2400 KB
30_IH19980412 TLE 2105 ms 2524 KB
30_camypaper AC 34 ms 2772 KB
30_dnk TLE 2102 ms 2524 KB
30_ei1333 TLE 2101 ms 2524 KB
30_japlj AC 34 ms 2772 KB
30_joisino TLE 2102 ms 2524 KB
30_maroonrk TLE 2101 ms 2524 KB
30_rickytheta TLE 2102 ms 2524 KB
30_satashun TLE 2102 ms 2524 KB
30_satos TLE 2102 ms 2524 KB
30_semiexp TLE 2102 ms 2400 KB
30_sigma425 AC 36 ms 2900 KB
30_sugim48 TLE 2106 ms 2524 KB
30_tozangezan TLE 2102 ms 2524 KB
30_wo01 TLE 2105 ms 2524 KB
30_yosupo AC 36 ms 2772 KB