Submission #2388088
Source Code Expand
using System; using System.Linq; using System.Collections.Generic; using Debug = System.Diagnostics.Debug; using SB = System.Text.StringBuilder; //using Number = ModInt; //using System.Numerics; //using static System.Math; namespace Program { public class Solver { Random rnd = new Random(0); public void Solve() { var a = rs; var b = rs; if (a == b) { Console.WriteLine(0); } else if (b == new string('0', a.Length)) { Console.WriteLine(-1); } else { var ret = solve(a, b); a = a.Reverse().AsString(); b = b.Reverse().AsString(); ret = Math.Min(ret, solve(a, b)); Console.WriteLine(ret); } } int solve(string s, string t) { var ret = 1 << 30; var n = s.Length; var L = new int[n]; var R = new int[n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) if (t[(i - j + n) % n] == '1') { L[i] = j; break; } for (int j = 0; j < n; j++) if (t[(i + j) % n] == '1') { R[i] = j; break; } } var erase = Enumerate(n + 5, x => new List<int>()); //最終的に右に i 回シフトした位置になるとき var set = new int[n + 5]; set[0]++; for (int i = 0; i < n; i++) { var diff = 0; for (int j = 0; j < n; j++) { if (s[(i + j) % n] == t[j]) continue; erase[L[j]].Add(R[j]); set[R[j]]++; diff++; } var ptr = 0; for (int j = n - 1; j >= 0; j--) if (set[j] > 0) { ptr = j; break; } //左に a 回シフトしたとき for (int a = 0; a < n; a++) { foreach (var x in erase[a]) set[x]--; erase[a].Clear(); while (set[ptr] == 0) ptr--; var b = ptr; //l->r ret = Math.Min(ret, diff + 2 * a + b + calc(n, b, i)); //r->l ret = Math.Min(ret, diff + 2 * b + a + calc(n, (n - a) % n, i)); } } return ret; } int calc(int n, int s, int t) { var d = Math.Abs(t - s); return Math.Min(d, n - d); } const long INF = 1L << 60; static int[] dx = { -1, 0, 1, 0 }; static int[] dy = { 0, 1, 0, -1 }; const string URDL = "URDL"; int ri { get { return sc.Integer(); } } long rl { get { return sc.Long(); } } double rd { get { return sc.Double(); } } string rs { get { return sc.Scan(); } } 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(ie.ToArray()); } static public string AsJoinedString<T>(this IEnumerable<T> ie, string st = " ") { return string.Join(st, ie); } static public void Main() { Console.SetOut(new Program.IO.Printer(Console.OpenStandardOutput()) { AutoFlush = false }); var solver = new Program.Solver(); try { solver.Solve(); Console.Out.Flush(); } catch { } } } #endregion #region Ex namespace Program.IO { using System.IO; using System.Text; using System.Globalization; public class Printer: StreamWriter { public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } } public Printer(Stream stream) : base(stream, new UTF8Encoding(false, true)) { } } 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 != 0; b = (char)read()) if (b != '\r') sb.Append(b); return sb.ToString(); } public long Long() { return isEof ? long.MinValue : long.Parse(Scan()); } public int Integer() { return isEof ? int.MinValue : int.Parse(Scan()); } public double Double() { return isEof ? double.NaN : double.Parse(Scan(), CultureInfo.InvariantCulture); } } } #endregion
Submission Info
Submission Time | |
---|---|
Task | D - Shift and Flip |
User | camypaper |
Language | C# (Mono 4.6.2.0) |
Score | 1000 |
Code Size | 5910 Byte |
Status | AC |
Exec Time | 721 ms |
Memory | 13308 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1000 / 1000 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 26 ms | 13268 KB |
sample_02.txt | AC | 20 ms | 9044 KB |
sample_03.txt | AC | 25 ms | 11348 KB |
sample_04.txt | AC | 25 ms | 11348 KB |
subtask_1_01.txt | AC | 21 ms | 11092 KB |
subtask_1_02.txt | AC | 25 ms | 11348 KB |
subtask_1_03.txt | AC | 21 ms | 9044 KB |
subtask_1_04.txt | AC | 21 ms | 11092 KB |
subtask_1_05.txt | AC | 505 ms | 11108 KB |
subtask_1_06.txt | AC | 21 ms | 11092 KB |
subtask_1_07.txt | AC | 21 ms | 11092 KB |
subtask_1_08.txt | AC | 21 ms | 11092 KB |
subtask_1_09.txt | AC | 25 ms | 13268 KB |
subtask_1_10.txt | AC | 26 ms | 9300 KB |
subtask_1_11.txt | AC | 529 ms | 9084 KB |
subtask_1_12.txt | AC | 530 ms | 9212 KB |
subtask_1_13.txt | AC | 553 ms | 11132 KB |
subtask_1_14.txt | AC | 661 ms | 11132 KB |
subtask_1_15.txt | AC | 646 ms | 13180 KB |
subtask_1_16.txt | AC | 597 ms | 9212 KB |
subtask_1_17.txt | AC | 594 ms | 13308 KB |
subtask_1_18.txt | AC | 538 ms | 11132 KB |
subtask_1_19.txt | AC | 546 ms | 13180 KB |
subtask_1_20.txt | AC | 531 ms | 13180 KB |
subtask_1_21.txt | AC | 599 ms | 11132 KB |
subtask_1_22.txt | AC | 608 ms | 11132 KB |
subtask_1_23.txt | AC | 721 ms | 9084 KB |
subtask_1_24.txt | AC | 704 ms | 11132 KB |
subtask_1_25.txt | AC | 711 ms | 11132 KB |
subtask_1_26.txt | AC | 26 ms | 11220 KB |
subtask_1_27.txt | AC | 31 ms | 13268 KB |
subtask_1_28.txt | AC | 56 ms | 13268 KB |
subtask_1_29.txt | AC | 155 ms | 11324 KB |
subtask_1_30.txt | AC | 563 ms | 11132 KB |
subtask_1_31.txt | AC | 24 ms | 9172 KB |
subtask_1_32.txt | AC | 26 ms | 11348 KB |
subtask_1_33.txt | AC | 31 ms | 13268 KB |
subtask_1_34.txt | AC | 57 ms | 11220 KB |
subtask_1_35.txt | AC | 159 ms | 11196 KB |
subtask_1_36.txt | AC | 571 ms | 11132 KB |
subtask_1_37.txt | AC | 27 ms | 13268 KB |
subtask_1_38.txt | AC | 30 ms | 11220 KB |
subtask_1_39.txt | AC | 57 ms | 11220 KB |
subtask_1_40.txt | AC | 153 ms | 11196 KB |
subtask_1_41.txt | AC | 525 ms | 13180 KB |
subtask_1_42.txt | AC | 528 ms | 11132 KB |
subtask_1_43.txt | AC | 576 ms | 11132 KB |
subtask_1_44.txt | AC | 569 ms | 13180 KB |
subtask_1_45.txt | AC | 560 ms | 11260 KB |
subtask_1_46.txt | AC | 554 ms | 9212 KB |