CSES - Putka Open 2020 – 4/5

CSES - Putka Open 2020 – 4/5 - Results

Submission details
Task:	Ruudukko
Sender:	ollpu
Submission time:	2020-11-08 22:23:44 +0200
Language:	C++ (C++17)
Status:	READY
Result:	100

Feedback
group	verdict	score
#1	ACCEPTED	5
#2	ACCEPTED	12
#3	ACCEPTED	27
#4	ACCEPTED	28
#5	ACCEPTED	28

Test results
test	verdict	time	group
#1	ACCEPTED	0.01 s	1, 5	details
#2	ACCEPTED	0.01 s	2, 5	details
#3	ACCEPTED	0.01 s	3, 5	details
#4	ACCEPTED	0.01 s	4, 5	details
#5	ACCEPTED	0.07 s	5	details
#6	ACCEPTED	0.03 s	5	details
#7	ACCEPTED	0.01 s	2, 5	details
#8	ACCEPTED	0.01 s	2, 5	details
#9	ACCEPTED	0.01 s	3, 5	details
#10	ACCEPTED	0.01 s	3, 5	details
#11	ACCEPTED	0.01 s	3, 5	details
#12	ACCEPTED	0.01 s	3, 5	details
#13	ACCEPTED	0.01 s	4, 5	details
#14	ACCEPTED	0.03 s	5	details
#15	ACCEPTED	0.01 s	3, 5	details
#16	ACCEPTED	0.05 s	5	details

Code

#include <bits/stdc++.h>
using namespace std;
constexpr int ctod(char c) {
  if (c == 'U') return 0;
  if (c == 'R') return 1;
  if (c == 'D') return 2;
  return 3;
}
constexpr char dtoc(int d) {
  return "URDL"[d];
}
template<typename After>
struct WLOGGuard {
  bool active;
  After lambda;
  WLOGGuard(bool a, After _) : active(a), lambda(_) {}
  ~WLOGGuard() { if (active) lambda(); }
};
map<array<int, 6>, int> poss_cache;
struct G {
  int n, m, X1, Y1, X2, Y2;
  vector<int> result;
  bool possible=0;
  void impossible() {
    possible = 0;
  }
  bool iex(int x) { return x == 0 || x == n-1; };
  bool iey(int y) { return y == 0 || y == m-1; };
  bool ic(int x, int y) { return iex(x) && iey(y); };
  bool ie(int x, int y) { return iex(x) || iey(y); };
  
  auto WLOGrev(bool cond=false) {
    if (!cond) {
      swap(X1, X2);
      swap(Y1, Y2);
    }
    return WLOGGuard(!cond, [&]() {
      reverse(result.begin(), result.end());
      if (wres) for (int &d : result) {
        d = (d+2)%4;
      }
      swap(X1, X2);
      swap(Y1, Y2);
    });
  }
  auto WLOGflipx(bool cond=false) {
    if (!cond) {
      X1 = n-X1-1;
      X2 = n-X2-1; 
    }
    return WLOGGuard(!cond, [&]() {
      if (wres) for (int &d : result) {
        if (d%2 == 0) d = (d+2)%4;
      }
      X2 = n-X2-1; 
      X1 = n-X1-1;
    });
  }
  auto WLOGflipy(bool cond=false) {
    if (!cond) {
      Y1 = m-Y1-1;
      Y2 = m-Y2-1; 
    }
    return WLOGGuard(!cond, [&]() {
      if (wres) for (int &d : result) {
        if (d%2 == 1) d = (d+2)%4;
      }
      Y2 = m-Y2-1; 
      Y1 = m-Y1-1;
    });
  }
  auto WLOGtranspose(bool cond=false) {
    if (!cond) {
      swap(n, m);
      swap(X1, Y1);
      swap(X2, Y2);
    }
    return WLOGGuard(!cond, [&]() {
      if (wres) for (int &d : result) {
        if (d%2) d = (d+1)%4;
        else d = (d+3)%4;
      }
      swap(n, m);
      swap(X1, Y1);
      swap(X2, Y2);
    });
  }
  
  bool wres;
  G(int _n, int _m, int _X1, int _Y1, int _X2, int _Y2, bool wr=1) : n(_n), m(_m), X1(_X1), Y1(_Y1), X2(_X2), Y2(_Y2), wres(wr)  {
    if (X1 < 0 || X1 >= n || Y1 < 0 || Y1 >= m) return;
    if (X2 < 0 || X2 >= n || Y2 < 0 || Y2 >= m) return;
    if (X1 == X2 && Y1 == Y2) {
      if (n == 1 && m == 1) {
        possible = 1;
      }
      return;
    }
    if ((n*m-1)%2 != (abs(X1-X2)+abs(Y1-Y2))%2) return;
    possible = 1;
    
    auto it = poss_cache.find({n, m, X1, Y1, X2, Y2});
    if (it != poss_cache.end()) {
      if (!wr || !it->second) {
        possible = it->second;
        return;
      }
    }
    solve();
    poss_cache[{n, m, X1, Y1, X2, Y2}] = possible;
  }
  void promote() {
    if (!wres && possible) {
      wres = 1;
      result.clear();
      solve();
    }
  }
  void cc(const G &g) {
    if (wres) {
      result.insert(result.end(), g.result.begin(), g.result.end());
    }
  }
  void cc(string sq) {
    if (wres) {
      for (char c : sq) result.push_back(ctod(c));
    }
  }
  void solve() {
    if (n == 1 || m == 1) {
      auto w1 = WLOGtranspose(n == 1);
      auto w2 = WLOGrev(Y1 < Y2);
      if (Y1 != 0 || Y2 != m-1) return impossible();
      cc(string(m-1, 'R'));
      return;
    }
    if (ic(X1, Y1) && ic(X2, Y2)) {
      auto w1 = WLOGflipx(X1 == 0);
      auto w2 = WLOGflipy(Y1 == 0);
      auto w3 = WLOGtranspose(X2 == 0 || (X1 != X2 && Y1 != Y2 && m%2));
      bool weird = X2 == 0 && m%2 == 1;
      for (int j = 0; j < (weird ? m-2 : m); ++j) {
        cc(G(n, 1, j%2 ? n-1 : 0, 0,  j%2 ? 0 : n-1, 0));
        if (j != m-1) cc("R");
      }
      if (weird) cc(G(n, 2, n-1, 0, 0, 1));
      return;
    }
    if (abs(X1-X2)+abs(Y1-Y2) == 1 && (ie(X1, Y1) != ie(X2, Y2))) {
      auto w1 = WLOGrev(ie(X1, Y1));
      auto w2 = WLOGflipx(X1 == 0);
      auto w3 = WLOGtranspose(X1 == 0);
      auto w4 = WLOGflipx(X1 == 0);
      for (int flp = 0; flp < 2; ++flp) {
        auto w5 = WLOGflipy(flp);
        for (int x : {2, n-1}) {
          auto g1 = G(n, Y1, 0, Y1-1, x, Y1-1, false);
          if (!g1.possible) continue;
          auto g2 = G(n-2, 1, x-2, 0, x == 2 ? n-3 : 0, false);
          if (!g2.possible) continue;
          auto g3 = G(n, m-Y1-1, x == 2 ? n-1 : 2, 0, 1, 0, false);
          if (!g3.possible) continue;
          if (!wres) return;
          g1.promote();
          g2.promote();
          g3.promote();
          cc("L");
          cc(g1);
          cc("R");
          cc(g2);
          cc("R");
          cc(g3);
          cc("L");
          return;
        }
        for (int x : {n-1}) {
          auto g1 = G(n, Y1, 0, Y1-1, x, Y1-1, false);
          if (!g1.possible) continue;
          auto g2 = G(n, m-Y1-1, x, 0, x-1, 0, false);
          if (!g2.possible) continue;
          auto g3 = G(n-3, 1, n-4, 0, 0, 0, false);
          if (!g3.possible) continue;
          if (!wres) return;
          g1.promote();
          g2.promote();
          g3.promote();
          cc("L");
          cc(g1);
          cc("RR");
          cc(g2);
          cc("L");
          cc(g3);
          cc("U");
          return;
        }
      }
    }
    if ((n == 3 && iex(X1) && iex(X2) && abs(Y1-Y2) <= 1) || (m == 3 && iey(Y1) && iey(Y2) && abs(X1-X2) <= 1)) {
      auto w1 = WLOGtranspose(n == 3 && iex(X1) && iex(X2) && abs(Y1-Y2) <= 1);
      if (X1 != X2) {
        auto w2 = WLOGflipy(Y1 >= Y2);
        auto w3 = WLOGflipx(X1 == 0);
        auto g1 = G(3, Y2, 0, Y2-1, 1, Y2-1, false);
        auto g2 = G(3, m-Y1-1, 1, 0, 2, 0, false);
        bool wide = Y1 != Y2;
        if (g1.possible && g2.possible) {
          g1.promote();
          g2.promote();
          cc("L");
          if (wide) cc("L");
          cc(g1);
          cc("RR");
          if (wide) cc("R");
          cc(g2);
          cc("L");
          if (wide) cc("L");
          return;
        }
      }
    }
    for (int rev = 0; rev < 2; ++rev) {
      auto w1 = WLOGrev(rev);
      auto w2 = WLOGtranspose(Y1 != Y2);
      auto w3 = WLOGflipy(Y1 < Y2);
      auto w4 = WLOGflipx(X1 >= X2);
      if (Y1 == 0 || X1 == n-1) continue;
      for (int fx = 0; fx <= (X1 == X2); ++fx) {
        auto w5 = WLOGflipx(!fx);
        for (int Cy = 0; Cy < 2 && Cy < Y1; ++Cy) {
          auto g1 = G(1, Y1-Cy, 0, Y1-1-Cy, 0, 0);
          auto g2 = G(n-X1-1, m, 0, 1+Cy, 0, 0, false);
          if (!g2.possible) continue;
          for (int x : {0, 1}) {
            auto g3 = G(X1, Y1+1, X1-1, Cy, x, Y1, false);
            if (!g3.possible) continue;
            auto g4 = G(X1+1, m-Y1-1, x, 0, X2, Y2-Y1-1, false);
            if (!g4.possible) continue;
            if (!wres) return;
            g2.promote();
            g3.promote();
            g4.promote();
            cc(g1);
            cc("D");
            cc(g2);
            if (Cy) cc("URU");
            else cc("UU");
            cc(g3);
            cc("R");
            cc(g4);
            return;
          }
        }
      }
    }
    {
      auto w1 = WLOGflipx(X1 <= X2);
      auto w2 = WLOGflipy(Y1 <= Y2);
      auto w3 = WLOGtranspose(Y1 != Y2);
      for (int transp = 0; transp <= (X1 != X2); ++transp) {
        auto w4 = WLOGtranspose(!transp);
        for (int x : {0, 1, n-2, n-1}) {
          auto g1 = G(n, Y1+1, X1, Y1, x, Y1, false);
          if (!g1.possible) continue;
          auto g2 = G(n, m-Y1-1, x, 0, X2, Y2-Y1-1, false);
          if (!g2.possible) continue;
          if (!wres) return;
          g1.promote();
          g2.promote();
          cc(g1);
          cc("R");
          cc(g2);
          return;
        }
        if (Y2-Y1 > 1)
        for (int x : {0, 1, n-2, n-1}) {
          auto g1 = G(n, Y1+2, X1, Y1, x, Y1+1, false);
          if (!g1.possible) continue;
          auto g2 = G(n, m-Y1-2, x, 0, X2, Y2-Y1-2, false);
          if (!g2.possible) continue;
          if (!wres) return;
          g1.promote();
          g2.promote();
          cc(g1);
          cc("R");
          cc(g2);
          return;
        }
      }
    }
    return impossible();
  }
  bool print() {
    cout << n << " " << m << ": " << X1 << "," << Y1 << " " << X2 << "," << Y2 << endl;
    return false;
  }
};
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int T;
  cin >> T;
  for (int Ti = 0; Ti < T; ++Ti) {
    int n, m, X1, Y1, X2, Y2;
    cin >> n >> m >> X1 >> Y1 >> X2 >> Y2;
    X1--; Y1--; X2--; Y2--;
    G g(n, m, X1, Y1, X2, Y2);
    if (g.possible) {
      int z[n][m] {};
      int x = X1, y = Y1;
      z[x][y] = 1;
      for (int d : g.result) {
        if (d == 0) x--;
        if (d == 1) y++;
        if (d == 2) x++;
        if (d == 3) y--;
        if (x < 0 || x >= n || y < 0 || y >= m) throw;
        if (z[x][y]) throw;
        z[x][y] = 1;
      }
      if (x != X2 || y != Y2) throw;
      cout << "YES\n";
      for (int d : g.result) cout << dtoc(d);
      cout << "\n";
    } else cout << "NO\n";
  }
}

Test details

Test 1

Group: 1, 5

Verdict: ACCEPTED

input
`100 1 45 1 45 1 1 1 18 1 1 1 10 1 47 1 17 1 30 1 33 1 28 1 20 ...` view save

correct output
`YES LLLLLLLLLLLLLLLLLLLLLLLLLLLLLL...` view save

user output
`YES LLLLLLLLLLLLLLLLLLLLLLLLLLLLLL...` Truncated

Test 2

Group: 2, 5

Verdict: ACCEPTED

input
`100 2 43 1 33 1 21 2 2 1 1 2 2 2 32 1 1 2 8 2 14 1 12 1 14 ...` view save

correct output
`NO NO NO NO YES ...` view save

user output
`NO NO NO NO YES ...` Truncated

Test 3

Group: 3, 5

Verdict: ACCEPTED

input
`100 3 4 2 1 2 4 3 38 2 24 1 22 3 29 2 23 2 3 3 8 3 1 1 2 ...` view save

correct output
`NO NO NO YES RRRRRRRUULDLULDLULDLLUR ...` view save

user output
`NO NO NO YES RRRRRRRUULDLULDLULDLLUR ...` Truncated

Test 4

Group: 4, 5

Verdict: ACCEPTED

input
`100 4 25 2 19 1 5 4 13 3 10 4 12 4 7 3 1 4 2 4 23 1 19 2 5 ...` view save

correct output
`YES DDRRRRRRULLLLLURRRRRULLLLLLLDD...` view save

user output
`YES RRRRRDLLLLLLLLLLLLLLLLLLLLLLLD...` Truncated

Test 5

Group: 5

Verdict: ACCEPTED

input
`100 16 8 13 1 14 8 41 21 19 11 32 12 46 17 13 7 6 11 8 41 4 32 4 12 ...` view save

correct output
`NO YES LURULURULURULURULURRDDDDDDDDDR...` view save

user output
`NO YES DDDDDDDDDDDDDLLLLLLLLLLURRRRRR...` Truncated

Test 6

Group: 5

Verdict: ACCEPTED

input
`100 31 38 18 35 31 37 35 48 7 13 21 21 46 21 25 2 4 19 35 2 13 2 35 1 ...` view save

correct output
`YES LLLLLLLLLLLLDRRRRRRRRRRRRDLLLL...` view save

user output
`YES LLLLLLLLLLLLLLLLLLLLLLLLLLLLLL...` Truncated

Test 7

Group: 2, 5

Verdict: ACCEPTED

input
`100 2 4 1 3 1 4 2 4 2 2 1 1 2 4 2 3 1 2 2 4 2 3 1 4 ...` view save

correct output
`YES LLDRRRU NO NO NO ...` view save

user output
`YES LLDRRRU NO NO NO ...` Truncated

Test 8

Group: 2, 5

Verdict: ACCEPTED

input
`100 2 5 1 2 2 4 2 5 1 2 1 1 2 5 2 1 1 2 2 5 1 1 1 5 ...` view save

correct output
`YES LDRRURRDL YES RRRDLLLLU NO ...` view save

user output
`YES LDRRURRDL YES RRRDLLLLU NO ...` Truncated

Test 9

Group: 3, 5

Verdict: ACCEPTED

input
`100 3 4 1 1 2 3 3 4 2 4 3 2 3 4 2 1 3 1 3 4 1 4 3 4 ...` view save

correct output
`YES DDRRRUULLDR NO YES URRRDDLULDL ...` view save

user output
`YES DDRUURRDDLU NO YES URDRURDDLLL ...` Truncated

Test 10

Group: 3, 5

Verdict: ACCEPTED

input
`100 3 5 3 4 3 2 3 5 3 5 2 3 3 5 3 1 2 2 3 5 3 1 3 2 ...` view save

correct output
`NO NO YES UURRRRDDLULDLU NO ...` view save

user output
`NO NO YES UURRRRDDLULDLU NO ...` Truncated

Test 11

Group: 3, 5

Verdict: ACCEPTED

input
`100 3 8 2 8 1 2 3 8 2 4 1 7 3 8 3 4 2 7 3 8 2 5 3 1 ...` view save

correct output
`NO NO NO YES LLLDRRRRURDRUULLLLLLLDD ...` view save

user output
`NO NO NO YES DRURDRUULLLLLLLDRRRDLLL ...` Truncated

Test 12

Group: 3, 5

Verdict: ACCEPTED

input
`100 3 9 1 3 2 9 3 9 1 6 1 5 3 9 3 6 2 8 3 9 3 2 3 4 ...` view save

correct output
`NO NO NO NO NO ...` view save

user output
`NO NO NO NO NO ...` Truncated

Test 13

Group: 4, 5

Verdict: ACCEPTED

input
`100 4 4 2 2 1 4 4 4 4 1 2 2 4 4 2 1 4 3 4 4 3 1 3 3 ...` view save

correct output
`YES DDLUUURRDDDRUUU YES UUURRRDLDRDLLUU NO ...` view save

user output
`YES DRRDLLLUUURRDRU YES UUURRRDDDLLURUL NO ...` Truncated

Test 14

Group: 5

Verdict: ACCEPTED

input
`100 12 27 6 22 1 8 6 25 3 2 4 4 6 16 4 6 5 2 36 33 8 6 1 6 ...` view save

correct output
`YES DLDDDDDRUUUURDDDDRUURDDRRULURU...` view save

user output
`YES RRRRDLLLLLLLLLLLLLLLLLLLLLLLLL...` Truncated

Test 15

Group: 3, 5

Verdict: ACCEPTED

input
`100 3 12 3 5 1 4 3 20 3 19 2 19 3 34 3 9 2 9 3 38 2 15 3 15 ...` view save

correct output
`YES RRRRRRRUULDLULDLULDLULDLDLULDL...` view save

user output
`YES RRRRRRRUULDLULDLULDLULDLDLULDL...` Truncated

Test 16

Group: 5

Verdict: ACCEPTED

input
`100 50 50 29 1 16 21 50 50 37 5 23 48 50 50 32 22 45 24 50 50 6 28 12 37 ...` view save

correct output
`YES DDDDDDDDDDDDDDDDDDDDDRUUUUUUUU...` view save

user output
`YES DDDDDDDDDDDDDDDDDDDDDRUUUUUUUU...` Truncated

Putka Open 2020 – 4/5

Ruudukko

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Tasks

Submissions (ollpu)