Submission #19019541


Source Code Expand

Copy
import std.conv, std.functional, std.range, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons;
import core.bitop;

class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }
real readReal() { return readToken.to!real; }

bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }

int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }
int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }
int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }


alias Pt = Tuple!(int, "x", int, "y");
enum INF = 10^^8;

void main() {
    try {
    for (; ; ) {
      const N = readInt();
      auto P = new Pt[N];
      foreach (i; 0 .. N) {
        P[i].x = readInt() - 1;
        P[i].y = readInt() - 1;
      }
      
      Pt[] ps;
      foreach (i; 0 .. N) {
        ps ~= Pt(P[i].x % 2, P[i].y % 3);
        ps ~= Pt(P[i].x    , P[i].y % 3);
        ps ~= Pt(P[i].x % 2, P[i].y    );
      }
      ps.sort;
      Pt[] qs;
      foreach (grp; ps.group) {
        if (grp[1] & 1) {
          qs ~= grp[0];
        }
      }
      debug {
        writeln("qs = ", qs);
      }
      
      int[int][2] ass;
      int[int][3] bss;
      foreach (p; qs) {
        if (p.x >= 2) {
          ass[p.x % 2][p.x] += 1;
        }
        if (p.y >= 3) {
          bss[p.y % 3][p.y] += 1;
        }
      }
      int[2][2] dpA;
      foreach (r; 0 .. 2) {
        dpA[r] = [0, 3];
      }
      int[2][3] dpB;
      foreach (s; 0 .. 3) {
        dpB[s] = [0, 2];
      }
      foreach (r; 0 .. 2) {
        foreach (x, a; ass[r]) {
          int[2] nxt = [INF, INF];
          foreach (t; 0 .. 2) {
            chmin(nxt[t], dpA[r][t] + a);
            chmin(nxt[t ^ 1], dpA[r][t] + (3 - a));
          }
          dpA[r] = nxt;
        }
      }
      foreach (s; 0 .. 3) {
        foreach (y, b; bss[s]) {
          int[2] nxt = [INF, INF];
          foreach (t; 0 .. 2) {
            chmin(nxt[t], dpB[s][t] + b);
            chmin(nxt[t ^ 1], dpB[s][t] + (2 - b));
          }
          dpB[s] = nxt;
        }
      }
      debug {
        writeln("dpA = ", dpA);
        writeln("dpB = ", dpB);
      }
      
      int[3][2] fs;
      foreach (p; qs) {
        if (p.x < 2 && p.y < 3) {
          fs[p.x][p.y] ^= 1;
        }
      }
      int ans = INF;
      foreach (u; 0 .. 1 << 5) {
        int[3][2] gs;
        foreach (r; 0 .. 2) foreach (s; 0 .. 3) {
          gs[r][s] = fs[r][s];
        }
        int cost;
        foreach (r; 0 .. 2) {
          if ((u >> r) & 1) {
            foreach (s; 0 .. 3) {
              gs[r][s] ^= 1;
            }
          }
          cost += dpA[r][(u >> r) & 1];
        }
        foreach (s; 0 .. 3) {
          if ((u >> (2 + s)) & 1) {
            foreach (r; 0 .. 2) {
              gs[r][s] ^= 1;
            }
          }
          cost += dpB[s][(u >> (2 + s)) & 1];
        }
        int cnt;
        foreach (r; 0 .. 2) foreach (s; 0 .. 3) {
          cnt += gs[r][s];
        }
        cost += min(cnt, 6 - cnt);
        chmin(ans, cost);
      }
      writeln(ans);
    }
  } catch (EOFException e) {
  }
}

Submission Info

Submission Time
Task C - Flipper
User hos_lyric
Language D (LDC 1.20.1)
Score 0
Code Size 3907 Byte
Status WA
Exec Time 94 ms
Memory 17852 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1300
Status
AC × 1
AC × 2
WA × 56
Set Name Test Cases
Sample example0.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, 044.txt, 045.txt, 046.txt, 047.txt, 048.txt, 049.txt, 050.txt, 051.txt, 052.txt, 053.txt, 054.txt, 055.txt, 056.txt, example0.txt
Case Name Status Exec Time Memory
000.txt WA 66 ms 7812 KB
001.txt WA 6 ms 3532 KB
002.txt WA 51 ms 6904 KB
003.txt WA 82 ms 8040 KB
004.txt WA 55 ms 7468 KB
005.txt WA 34 ms 5168 KB
006.txt WA 72 ms 9640 KB
007.txt WA 65 ms 8164 KB
008.txt WA 54 ms 11000 KB
009.txt WA 80 ms 10100 KB
010.txt WA 48 ms 6236 KB
011.txt WA 94 ms 11356 KB
012.txt WA 21 ms 4932 KB
013.txt WA 45 ms 6240 KB
014.txt WA 23 ms 5236 KB
015.txt WA 75 ms 16784 KB
016.txt WA 72 ms 7592 KB
017.txt WA 8 ms 3552 KB
018.txt WA 28 ms 4364 KB
019.txt WA 33 ms 5172 KB
020.txt WA 54 ms 7484 KB
021.txt WA 37 ms 5736 KB
022.txt WA 39 ms 6984 KB
023.txt WA 22 ms 4944 KB
024.txt WA 44 ms 7212 KB
025.txt AC 4 ms 3404 KB
026.txt WA 45 ms 5412 KB
027.txt WA 40 ms 5356 KB
028.txt WA 48 ms 5472 KB
029.txt WA 45 ms 5408 KB
030.txt WA 47 ms 5404 KB
031.txt WA 46 ms 5464 KB
032.txt WA 84 ms 11724 KB
033.txt WA 86 ms 11924 KB
034.txt WA 92 ms 17852 KB
035.txt WA 90 ms 13856 KB
036.txt WA 89 ms 15696 KB
037.txt WA 89 ms 15652 KB
038.txt WA 89 ms 15876 KB
039.txt WA 85 ms 13768 KB
040.txt WA 90 ms 11912 KB
041.txt WA 85 ms 11904 KB
042.txt WA 88 ms 15828 KB
043.txt WA 88 ms 15760 KB
044.txt WA 83 ms 11740 KB
045.txt WA 84 ms 11716 KB
046.txt WA 90 ms 15748 KB
047.txt WA 83 ms 11812 KB
048.txt WA 90 ms 15852 KB
049.txt WA 86 ms 11852 KB
050.txt WA 89 ms 15712 KB
051.txt WA 88 ms 11864 KB
052.txt WA 86 ms 11812 KB
053.txt WA 87 ms 15764 KB
054.txt WA 93 ms 16648 KB
055.txt WA 89 ms 16868 KB
056.txt WA 88 ms 11844 KB
example0.txt AC 4 ms 3308 KB