QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#354272#8315. Candy AdsPlentyOfPenaltyTL 1522ms395900kbC++149.5kb2024-03-15 02:16:582024-03-15 02:16:58

Judging History

你现在查看的是最新测评结果

  • [2024-03-15 02:16:58]
  • 评测
  • 测评结果:TL
  • 用时:1522ms
  • 内存:395900kb
  • [2024-03-15 02:16:58]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define cho(u, x) ((u) << 1 | (x))

const int N = 5e4 + 9, S = 380;
int n, m, w, h, bln[N], tot, tmp[N], now[N];
bool ans[N], use[N];
vector<vector<int>> G;

void myassert(int x) {
  if (!x) {
    cout << "assertion failed" << endl;
    exit(-1);
  }
}

int tim, col_tot;
vector<int> dfn, low, col, stk;
vector<char> ins;
void tarjan(int u) {
  dfn[u] = low[u] = ++tim;
  ins[u] = true, stk.push_back(u);
  for (int v : G[u])
    if (!dfn[v]) {
      tarjan(v);
      low[u] = min(low[u], low[v]);
    } else if (ins[v]) {
      low[u] = min(low[u], dfn[v]);
    }
  if (dfn[u] == low[u]) {
    ++col_tot;
    for (;;) {
      col[stk.back()] = col_tot;
      ins[stk.back()] = false;
      if (u == stk.back()) break;
      stk.pop_back();
    }
    stk.pop_back();
  }
}

struct point {
  int x, y;
};

struct atom {
  int l, r, id;
  point u;
  inline bool operator<(const atom &rhs) const { return r == rhs.r ? l < rhs.l : r < rhs.r; }
} a[N];

int newnode() {
  ++tot;
  if (G.size() <= static_cast<size_t>(tot * 2 + 10)) {
    G.resize(G.size() + N);
  }
  return tot;
}

void addedge(int u, int v) {
  // fprintf(stderr, ">>> add edge %d[%d] %d[%d] \n", u >> 1, u & 1, v >> 1, v & 1);
  G[u].emplace_back(v);
}

void check(int i, int j) {
  if (a[i].u.x < a[j].u.x) {
    if (a[i].u.x + w <= a[j].u.x) return;
  } else {
    if (a[j].u.x + w <= a[i].u.x) return;
  }
  if (a[i].u.y < a[j].u.y) {
    if (a[i].u.y + h <= a[j].u.y) return;
  } else {
    if (a[j].u.y + h <= a[i].u.y) return;
  }
  addedge(cho(i, 1), cho(j, 0));
  addedge(cho(j, 1), cho(i, 0));
}

int d, rt;
struct node {
  int x[2], l[2], r[2], ch[2], src, nod;
  bool operator<(const node &rhs) const { return x[d] < rhs.x[d]; }
} kdt[N];

inline void maintain(int u) {
  kdt[u].l[0] = kdt[u].x[0];
  if (kdt[u].ch[0] && kdt[kdt[u].ch[0]].l[0] < kdt[u].l[0]) kdt[u].l[0] = kdt[kdt[u].ch[0]].l[0];
  if (kdt[u].ch[1] && kdt[kdt[u].ch[1]].l[0] < kdt[u].l[0]) kdt[u].l[0] = kdt[kdt[u].ch[1]].l[0];
  kdt[u].l[1] = kdt[u].x[1];
  if (kdt[u].ch[0] && kdt[kdt[u].ch[0]].l[1] < kdt[u].l[1]) kdt[u].l[1] = kdt[kdt[u].ch[0]].l[1];
  if (kdt[u].ch[1] && kdt[kdt[u].ch[1]].l[1] < kdt[u].l[1]) kdt[u].l[1] = kdt[kdt[u].ch[1]].l[1];
  kdt[u].r[0] = kdt[u].x[0];
  if (kdt[u].ch[0] && kdt[kdt[u].ch[0]].r[0] > kdt[u].r[0]) kdt[u].r[0] = kdt[kdt[u].ch[0]].r[0];
  if (kdt[u].ch[1] && kdt[kdt[u].ch[1]].r[0] > kdt[u].r[0]) kdt[u].r[0] = kdt[kdt[u].ch[1]].r[0];
  kdt[u].r[1] = kdt[u].x[1];
  if (kdt[u].ch[0] && kdt[kdt[u].ch[0]].r[1] > kdt[u].r[1]) kdt[u].r[1] = kdt[kdt[u].ch[0]].r[1];
  if (kdt[u].ch[1] && kdt[kdt[u].ch[1]].r[1] > kdt[u].r[1]) kdt[u].r[1] = kdt[kdt[u].ch[1]].r[1];
}

int build(int l, int r, int k) {
  if (l > r) return 0;
  int mid = (l + r) >> 1;
  d = k;
  nth_element(kdt + l, kdt + mid, kdt + r + 1);
  kdt[mid].ch[0] = build(l, mid - 1, k ^ 1);
  kdt[mid].ch[1] = build(mid + 1, r, k ^ 1);
  maintain(mid);
  // fprintf(stderr, "build tree u=%d lc=%d rc=%d\n", mid, kdt[mid].ch[0], kdt[mid].ch[1]);
  return mid;
}

void query(int u, const node &cur) {
  if (cur.l[0] <= kdt[u].l[0] && cur.l[1] <= kdt[u].l[1] && kdt[u].r[0] <= cur.r[0] && kdt[u].r[1] <= cur.r[1]) {
    if (kdt[u].nod) {
      addedge(cho(cur.src, 1), cho(kdt[u].nod, 0));
      addedge(cho(kdt[u].nod, 1), cho(cur.src, 0));
    }
    return;
  }
  if (cur.l[0] > kdt[u].r[0] || cur.l[1] > kdt[u].r[1] || cur.r[0] < kdt[u].l[0] || cur.r[1] < kdt[u].l[1]) {
    return;
  }
  if (use[kdt[u].src] && cur.l[0] <= kdt[u].x[0] && cur.l[1] <= kdt[u].x[1] && kdt[u].x[0] <= cur.r[0] && kdt[u].x[1] <= cur.r[1]) {
    addedge(cho(cur.src, 1), cho(kdt[u].src, 0));
    addedge(cho(kdt[u].src, 1), cho(cur.src, 0));
  }
  query(kdt[u].ch[0], cur);
  query(kdt[u].ch[1], cur);
}

void assign(int u) {
  if (kdt[u].ch[0]) assign(kdt[u].ch[0]);
  if (kdt[u].ch[1]) assign(kdt[u].ch[1]);
int lc = kdt[u].ch[0],rc = kdt[u].ch[1];
  if (kdt[lc].nod && kdt[rc].nod) {
    kdt[u].nod = newnode();
    addedge(cho(kdt[u].nod, 0), cho(kdt[lc].nod, 0));
    addedge(cho(kdt[lc].nod, 1), cho(kdt[u].nod, 1));
    addedge(cho(kdt[u].nod, 0), cho(kdt[rc].nod, 0));
    addedge(cho(kdt[rc].nod, 1), cho(kdt[u].nod, 1));
    if (use[kdt[u].src]) {
      addedge(cho(kdt[u].nod, 0), cho(kdt[u].src, 0));
      addedge(cho(kdt[u].src, 1), cho(kdt[u].nod, 1));
    }
  } else if (kdt[lc].nod) {
    if (use[kdt[u].src]) {
      kdt[u].nod = newnode();
      addedge(cho(kdt[u].nod, 0), cho(kdt[lc].nod, 0));
      addedge(cho(kdt[lc].nod, 1), cho(kdt[u].nod, 1));
      addedge(cho(kdt[u].nod, 0), cho(kdt[u].src, 0));
      addedge(cho(kdt[u].src, 1), cho(kdt[u].nod, 1));
    } else {
      kdt[u].nod = kdt[lc].nod;
    }
  } else if (kdt[rc].nod) {
    if (use[kdt[u].src]) {
      kdt[u].nod = newnode();
      addedge(cho(kdt[u].nod, 0), cho(kdt[rc].nod, 0));
      addedge(cho(kdt[rc].nod, 1), cho(kdt[u].nod, 1));
      addedge(cho(kdt[u].nod, 0), cho(kdt[u].src, 0));
      addedge(cho(kdt[u].src, 1), cho(kdt[u].nod, 1));
    } else {
      kdt[u].nod = kdt[rc].nod;
    }
  } else {
    if (use[kdt[u].src]) {
      kdt[u].nod = kdt[u].src;
    } else {
      kdt[u].nod = 0;
    }
  }
  // fprintf(stderr, "assign %d use=%d src=%d nod=%d\n", u, use[kdt[u].src], kdt[u].src, kdt[u].nod);
}

struct block {
  int l, r;
  vector<int> q;
  void solve() {
    // fprintf(stderr, "solve block %d %d\n", l, r);
    for (int i = 1; i <= n; i++) use[i] = false;
    for (int x : q) use[x] = true;
    assign(rt);
    node cur;
    for (int i = l; i <= r; i++) {
      cur.l[0] = a[i].u.x - (w - 1), cur.r[0] = a[i].u.x + (w - 1);
      cur.l[1] = a[i].u.y - (h - 1), cur.r[1] = a[i].u.y + (h - 1);
      cur.src = i, cur.nod = -1;
      query(rt, cur);
    }
  }
} b[N / S + 9];

int main() {
#ifdef memset0
  // freopen("K.in", "r", stdin);
  // freopen("K-big.txt", "r", stdin);
  freopen("K-data.txt", "r", stdin);
#endif
  cin.tie(0)->sync_with_stdio(0);
  // vector<pair<int, int>> lim;
  cin >> n >> w >> h;
  for (int i = 1; i <= n; i++) {
    cin >> a[i].l >> a[i].r >> a[i].u.x >> a[i].u.y;
    a[i].id = i;
  }
  sort(a + 1, a + n + 1);
  // for (int i = 1; i <= n; i++) fprintf(stderr, "a[%d] => l=%d r=%d x=%d y=%d id=%d\n", i, a[i].l, a[i].r, a[i].u.x, a[i].u.y, a[i].id);
  for (int i = 1; i <= n; i++) {
    now[a[i].id] = i;
  }
  cin >> m;
  tot = n;
  G.resize(tot * 2 + N);
  for (int u, v, i = 1; i <= m; i++) {
    cin >> u >> v;
    // lim.emplace_back(u, v);
    u = now[u];
    v = now[v];
    addedge(cho(u, 0), cho(v, 1));
    addedge(cho(v, 0), cho(u, 1));
  }

  for (int i = 1; i <= n; i++) {
    kdt[i].src = i;
    kdt[i].x[0] = a[i].u.x;
    kdt[i].x[1] = a[i].u.y;
  }
  rt = build(1, n, 0);

  for (int i = 1; i <= n; i++) {
    bln[i] = i / S + 1;
    if (!b[bln[i]].l) b[bln[i]].l = i;
    b[bln[i]].r = i;
    // cout << bln[i] << " \n"[i == n];
  }
  for (int i = 1; i <= n; i++) tmp[i] = a[i].r;
  for (int ql, qr, i = 1; i <= n; i++) {
    ql = lower_bound(tmp + 1, tmp + i, a[i].l) - tmp;
    qr = i - 1;
    if (ql <= qr) {
      // fprintf(stderr, "solve [ql=%d[%d] qr=%d[%d]] i=%d\n", ql, bln[ql], qr, bln[qr], i);
      if (bln[ql] == bln[qr]) {
        for (int j = ql; j <= qr; j++) check(j, i);
      } else {
        for (int j = ql; j <= b[bln[ql]].r; j++) check(j, i);
        for (int j = b[bln[qr]].l; j <= qr; j++) check(j, i);
        for (int k = bln[ql] + 1; k < bln[qr]; k++) {
          b[k].q.emplace_back(i);
        }
      }
    }
  }
  for (int i = 1; i <= bln[n]; i++) {
    b[i].solve();
  }
#ifdef memset0
  int edg = 0;
  for (int i = cho(1, 0); i <= cho(tot, 1); i++) edg += G[i].size();
  cerr << "tot = " << tot << "; edg = " << edg << endl;
#endif

  dfn.resize((tot + 1) << 1);
  low.resize((tot + 1) << 1);
  col.resize((tot + 1) << 1);
  ins.resize((tot + 1) << 1);
  for (int i = cho(1, 0); i <= cho(tot, 1); i++)
    if (!dfn[i]) {
      tarjan(i);
    }
  for (int i = 1; i <= tot; i++)
    if (col[cho(i, 0)] == col[cho(i, 1)]) {
      cout << "No" << endl;
      return 0;
    }
  cout << "Yes" << endl;
  for (int i = 1; i <= n; i++) {
    ans[a[i].id] = col[cho(i, 0)] > col[cho(i, 1)];
  }
  // for (int i = 1; i <= n; i++) cerr << col[cho(i, 0)] << " \n"[i == n];
  // for (int i = 1; i <= n; i++) cerr << col[cho(i, 1)] << " \n"[i == n];
#ifdef ONLINE_JUDGE
  for (int i = 1; i <= n; i++) cout << ans[i];
  cout << endl;
#endif
#ifdef memset0
  cerr << "clock = " << clock() / (double)CLOCKS_PER_SEC << endl;
#endif

  // for (int i = 1; i <= n; i++) cerr << ans[i] << " \n"[i == n];
  // sort(a + 1, a + n + 1, [&](const atom &u, const atom &v) { return u.id < v.id; });
  // for (const auto &[u, v] : lim) {
  //   myassert(ans[u] || ans[v]);
  // }
  // for (int i = 1; i <= n; i++)
  //   if (ans[i])
  //     for (int j = i + 1; j <= n; j++)
  //       if (ans[j]) {
  //         // fprintf(stderr, ">> %d %d\n", i, j);
  //         if (a[i].r < a[j].l) continue;
  //         if (a[j].r < a[i].l) continue;
  //         if (a[i].u.x < a[j].u.x) {
  //           if (a[i].u.x + w <= a[j].u.x) continue;
  //         } else {
  //           if (a[j].u.x + w <= a[i].u.x) continue;
  //         }
  //         if (a[i].u.y < a[j].u.y) {
  //           if (a[i].u.y + h <= a[j].u.y) continue;
  //         } else {
  //           if (a[j].u.y + h <= a[i].u.y) continue;
  //         }
  //         myassert(0);
  //       }
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 4380kb

input:

2 2 2
1 2 1 1
2 3 2 2
1
1 2

output:

Yes
01

result:

ok accepted

Test #2:

score: 0
Accepted
time: 1ms
memory: 6512kb

input:

3 2 2
1 2 1 1
1 3 1 2
2 3 2 2
3
1 2
2 3
1 3

output:

No

result:

ok accepted

Test #3:

score: 0
Accepted
time: 0ms
memory: 4472kb

input:

10 3 3
2 3 7 10
1 3 9 6
3 5 2 1
4 5 8 9
4 7 1 7
3 4 4 4
6 8 9 5
1 3 6 7
2 5 7 4
6 9 9 9
10
9 1
6 2
8 5
9 5
10 4
5 1
3 2
10 9
9 5
8 2

output:

Yes
1010110101

result:

ok accepted

Test #4:

score: 0
Accepted
time: 1ms
memory: 6448kb

input:

10 2 4
2 5 4 8
8 10 6 3
1 3 7 3
8 10 7 9
1 2 2 6
3 6 9 2
4 7 2 10
8 9 7 4
8 9 7 1
1 2 9 8
8
2 4
6 5
1 4
6 9
9 5
6 3
6 8
8 2

output:

Yes
0101110000

result:

ok accepted

Test #5:

score: 0
Accepted
time: 0ms
memory: 6472kb

input:

10 4 3
8 9 8 8
4 5 6 8
8 9 3 2
5 7 10 6
6 7 7 9
3 5 7 3
9 10 9 4
4 7 9 2
9 10 8 2
3 5 1 8
14
8 10
10 1
1 10
6 4
2 3
9 6
8 6
5 2
9 8
1 9
10 7
1 6
10 8
3 6

output:

Yes
1011100111

result:

ok accepted

Test #6:

score: 0
Accepted
time: 1ms
memory: 6452kb

input:

100 94 194
1461 1945 694 1593
217 353 761 1920
695 982 452 599
1301 1757 662 1862
1355 1574 917 258
1253 1718 10 893
822 1112 623 748
597 925 1196 65
1277 1785 17 1368
1564 1914 1637 545
1363 1810 922 1988
1001 1251 28 156
1678 1978 185 980
1730 1823 145 1803
655 1040 981 1261
593 637 212 555
1358 1...

output:

Yes
1011101101111111010111111110110001011110111111111111011010100111101111111011111111101100111111111001

result:

ok accepted

Test #7:

score: 0
Accepted
time: 1ms
memory: 4416kb

input:

100 108 62
410 579 1353 353
82 560 288 988
32 392 1431 1904
1364 1785 1489 1395
1118 1448 301 1275
995 1149 127 1756
1607 1906 1 1907
1217 1782 291 764
616 840 1552 1006
787 1202 34 200
283 316 3 460
903 1356 822 1469
1110 1370 1144 1880
439 746 509 1376
47 344 73 1807
551 1032 280 851
612 631 262 1...

output:

Yes
0001101100011011011101110101001010101101011101101101100110101110110010110111110111101011110110010111

result:

ok accepted

Test #8:

score: 0
Accepted
time: 1ms
memory: 6556kb

input:

100 61 130
1234 1525 1544 1497
1696 1819 895 1801
1079 1222 1201 1725
1581 1827 420 1191
270 782 261 417
1620 1685 415 79
103 387 832 562
1461 1488 388 1124
1246 1726 1900 874
139 632 984 1770
708 882 1235 1378
98 432 867 560
316 863 1773 1122
782 1080 428 1748
1599 1695 590 1969
1384 1941 449 1137
...

output:

Yes
0110011110101111101100101111101101110111111111100111111100101111111101111101101101111011101110111011

result:

ok accepted

Test #9:

score: 0
Accepted
time: 0ms
memory: 6440kb

input:

1000 46 46
650 693 297 1278
322 411 1293 527
1613 1798 1513 1514
380 440 1463 1779
220 263 1459 1937
718 777 649 81
497 672 1224 818
576 597 977 1728
199 283 827 1766
248 259 1666 1199
956 1092 142 1966
1010 1159 414 186
592 728 1781 673
403 596 1021 1607
1118 1234 1511 417
810 830 1667 1125
1304 14...

output:

Yes
11111111101101100111001111111001111010101100111101111101111100011011110011111111110001111111111111111100111111111111101111101011011101111111111011111101011111111011110011101111111101101111111110110101110011111101110111011111111111111101110111111111001110110111110101100111101111010100011111111111...

result:

ok accepted

Test #10:

score: 0
Accepted
time: 0ms
memory: 6408kb

input:

1000 36 48
1100 1171 1599 1568
1906 1917 219 455
696 718 914 1154
407 562 1599 1749
1389 1535 744 1456
1791 1979 535 1206
597 670 389 111
131 171 1760 1858
770 928 1938 1633
1481 1537 1325 440
1667 1759 1038 837
869 1001 1114 1721
1523 1590 1412 1475
205 372 620 1395
1247 1396 113 1943
163 316 1852 ...

output:

Yes
11111111110111100001011111010101111001111010110111110111011010110111001111110100110001010011111110010011011011110110100011111001111111111111111111101000101101111110111111011000111111101101111110101011111111111011101111111111111111010111011101110111010111110111110111101111011111101110010111111101...

result:

ok accepted

Test #11:

score: 0
Accepted
time: 2ms
memory: 6484kb

input:

1000 37 46
174 204 1667 729
1866 1875 1884 556
792 945 1920 927
1303 1473 1163 1341
1519 1539 503 362
62 140 1262 1450
1235 1263 1031 1966
895 1057 215 1626
1135 1208 666 998
1459 1477 1941 1671
1050 1192 60 1375
137 244 1672 1445
217 414 724 1347
1043 1200 1401 68
1331 1495 919 933
1086 1137 1341 3...

output:

Yes
01111011011011011110101110111101110111110100011101110111100011111101110010111011110100110110011101111011010111111111101011111001111101111010000111001010111110101110111011111011111011001111010111100010011110110111111111110111010111111111111111110111010111111001110010110111100111110111111110111111...

result:

ok accepted

Test #12:

score: 0
Accepted
time: 217ms
memory: 34836kb

input:

50000 9 9
630 678 1889 1026
1568 1607 1637 114
732 830 1245 590
1023 1032 403 698
211 243 1531 1382
593 650 248 955
708 717 1688 1772
509 536 884 582
1798 1865 522 1714
333 390 75 1044
1494 1540 1320 1543
160 211 866 1215
1847 1906 1189 1636
154 198 1074 1193
1636 1705 227 1685
940 954 508 394
1266 ...

output:

Yes
10010010111010111111010111111000011110001111111111111110011110110111101111101110110011011110110101110011010110110111101110111111100011111011101101110011110101010111010101101011010101010110111110111101010111111101111011111101111111011110101111011111011111101111111100111101111011011101111111010011...

result:

ok accepted

Test #13:

score: 0
Accepted
time: 220ms
memory: 33580kb

input:

50000 10 6
282 331 1148 1597
676 739 296 677
294 305 1501 1969
1440 1499 862 104
1008 1072 131 1387
1036 1053 915 1390
1569 1662 1463 996
287 334 1662 173
358 381 383 367
481 550 156 361
1340 1389 671 76
986 1006 1634 353
445 465 596 1864
1422 1452 1740 1762
1381 1407 745 4
1172 1188 144 1320
751 79...

output:

Yes
11111111111111111100001111110100110111010111111101011111111010110111110111111010011111110111101011111110101100111101110101111111111011001111110111111111001111011111101100100110111111101111111111110011111110111111111111011111011110110101111011111111010111111111111111111101101011111011101010011111...

result:

ok accepted

Test #14:

score: 0
Accepted
time: 258ms
memory: 57016kb

input:

50000 7 15
107 197 820 713
1833 1863 671 1773
1573 1727 1976 1743
1656 1718 1714 926
1615 1734 113 378
182 285 1167 811
1924 1973 1809 178
972 1020 1877 100
25 46 1192 488
251 347 504 751
320 334 308 1545
554 619 166 1528
108 145 1283 1383
153 200 1714 494
390 537 1052 565
1331 1357 1638 327
87 161 ...

output:

No

result:

ok accepted

Test #15:

score: 0
Accepted
time: 1522ms
memory: 395900kb

input:

50000 130 164
26 1216 1021 1261
423 1110 383 616
772 1551 1399 245
42 811 1691 1783
28 1691 697 692
646 1607 1421 1684
312 1974 1671 86
212 905 73 226
149 517 215 924
1 1999 328 1453
1112 1934 831 1938
452 1041 1092 1108
752 1876 1394 1967
54 1919 1574 1188
1085 1608 502 1826
35 714 1023 312
191 655...

output:

No

result:

ok accepted

Test #16:

score: 0
Accepted
time: 839ms
memory: 317980kb

input:

50000 3 3
1234 1643 1739 1512
10 1933 22 20
1310 1636 411 1094
438 1464 670 124
25 1973 310 1595
645 1051 951 492
399 1201 1372 1480
348 1596 576 63
48 1485 427 1291
47 1809 173 1483
362 1020 1617 767
113 1855 269 1437
732 1154 125 700
1538 1731 721 1313
235 764 820 1204
197 1616 1981 1686
1546 1962...

output:

Yes
11101011111111101001101101101111101111110110100100011111111011011100101111101111010010110111011111011010110100111100111100111011101111111110011111111111100001111111010011010011110101111111110101011101111111111111110111111111111111111011011111111101111001000101011101010101100110101110101101111010...

result:

ok accepted

Test #17:

score: 0
Accepted
time: 849ms
memory: 318784kb

input:

50000 5 5
236 753 1756 1913
184 1557 1777 1450
1014 1832 286 44
532 1754 1644 1433
156 960 963 640
126 1056 1691 1258
22 1974 1989 1748
357 1569 219 1698
48 1001 719 1494
121 1645 1877 546
1180 1742 1332 214
383 1898 1419 304
564 600 314 1091
368 1475 1106 1828
186 1448 1362 1189
101 1909 17 868
52 ...

output:

No

result:

ok accepted

Test #18:

score: 0
Accepted
time: 1259ms
memory: 207576kb

input:

50000 666 699
1110 1202 13 682
1312 1528 1338 1796
1000 1135 139 330
239 397 1915 95
1085 1097 1159 1023
1804 1864 1192 1138
1463 1729 32 475
753 1045 396 1237
1007 1240 557 1427
1661 1669 1926 1652
761 1003 652 138
38 76 372 1604
48 216 1426 1190
475 561 249 1496
74 175 30 414
780 812 1877 640
1613...

output:

No

result:

ok accepted

Test #19:

score: 0
Accepted
time: 3ms
memory: 6648kb

input:

2000 16 11
1633 1643 527 35
472 486 815 1543
443 455 810 818
950 960 978 1156
473 486 724 837
1959 1974 1507 1666
487 499 1013 936
224 235 1791 787
498 508 1515 1157
1897 1911 619 188
1931 1946 1116 160
870 883 1056 1118
804 816 1736 1569
1634 1649 674 310
348 358 100 1512
1652 1661 1751 1787
440 45...

output:

Yes
01011001010101010101101000110011000000011101000000010101001010001110110000100111010001000011100101000110100101100100101011000110000010010100010101100110100001010110110001000100010101011011000000110000001000001011100010011111000110011000100001100000000010010001110000110101101001000111110001101111...

result:

ok accepted

Test #20:

score: 0
Accepted
time: 0ms
memory: 6736kb

input:

2000 20 30
1236 1251 1570 1767
1041 1079 1374 1150
1609 1627 1256 214
1872 1898 1597 1826
375 402 1983 1515
532 552 974 415
1417 1426 342 269
1393 1422 1613 1130
781 818 521 1080
982 1002 417 620
1601 1618 522 1261
90 124 1999 628
639 677 733 1295
808 839 763 979
1316 1346 1685 1882
391 421 201 1133...

output:

Yes
00011001101001000010100101101111100011100101010010111010001100100001000011101001011000001000100000101101011011101000101111101110000111001101101010111011101010110000000111001010111001101000101100111001110110000111000100010101111000110111010000110111111011010000101010001010101101000101100100100101...

result:

ok accepted

Test #21:

score: 0
Accepted
time: 781ms
memory: 298500kb

input:

50000 18 11
1 225 703 628
180 350 564 570
420 484 253 17
133 178 809 543
1 225 145 1761
1 225 1801 144
1 225 1441 914
226 450 253 1563
112 402 809 359
1 225 631 1508
226 450 145 1068
1 225 505 1101
1 225 1801 1717
77 240 89 1696
93 291 777 1168
221 282 66 1666
26 293 1587 1677
1 225 1369 1750
127 33...

output:

Yes
10001111011110000101001100001011011100101101111000101100011100101001001001011100001101011001111000101101010000101000000100000010100001011100111111000001001111000010000101100110111110100000100110011010001110100000010111011011111010011011111110000001101110010110101011000111000011011011101111110010...

result:

ok accepted

Test #22:

score: 0
Accepted
time: 754ms
memory: 286732kb

input:

50000 16 20
531 889 372 1589
1 291 1057 1401
1 291 65 1881
68 232 505 1634
239 642 937 799
292 582 593 481
211 281 1679 1025
1 291 1681 1781
1 291 1857 1561
292 582 1585 1221
410 863 806 71
1 291 193 1161
292 582 1681 441
131 508 1454 1362
420 775 1272 1586
437 881 961 1584
129 550 1775 606
1 291 18...

output:

Yes
01100101110110000111101111110110111010001011000110110111010011010110110101101100101101000110111010100100101110111111100101110011001010011100111100111000111101010110101101011110101111111010110111100111011010011010001001110011111111101110000101101100111001110101010000010000101000000001000001011101...

result:

ok accepted

Test #23:

score: 0
Accepted
time: 290ms
memory: 45368kb

input:

50000 65 64
1424 1489 230 1633
398 462 780 1133
1221 1281 1691 1729
1099 1159 1691 1025
367 427 781 1345
1099 1159 1496 193
550 610 1366 641
184 244 196 1729
320 382 1471 1569
1223 1282 1351 865
428 488 1951 1985
489 549 521 1345
245 305 66 1921
993 1052 1613 356
1038 1098 1626 65
514 578 977 1158
4...

output:

Yes
00111111001110100110100110001101110010110010111001001100010101110100001100111011110010111100011001111011111000101001000111010111011110110001011001000011011101011101001101011011111110100001110110100100100001010101101111010001011100010010110010101000111000111010111011111111011110011010010110011010...

result:

ok accepted

Test #24:

score: 0
Accepted
time: 413ms
memory: 147304kb

input:

50000 11 11
1 130 628 320
1 130 419 1717
1 130 1332 1695
1293 1413 654 1183
183 434 591 1584
1 130 1013 386
1 130 991 1574
587 637 510 1239
1906 1942 817 69
1 130 364 793
1256 1547 102 317
297 429 1556 253
1 130 1420 485
1 130 1200 1090
1 130 78 1475
203 282 1674 577
1 130 67 78
304 534 1296 1158
1 ...

output:

Yes
00011000101100000101010110001101100100011011000010001100000001000101101001010001110101100000110101000000001000100101101110110110001000000000010100110110100110100010000010110000101010010000001110101001110011111001000100100000000000001001000100010101010100101010100001011111101101000110000111010000...

result:

ok accepted

Test #25:

score: 0
Accepted
time: 467ms
memory: 149744kb

input:

50000 16 20
1302 1443 1425 26
1005 1299 1721 667
1 376 1185 121
377 752 1889 1481
377 752 897 1781
377 752 337 181
679 776 870 1151
460 522 1636 228
377 752 1361 681
377 752 1281 1781
377 752 1729 1281
474 553 1740 764
994 1403 1246 717
851 988 319 39
1 376 1121 181
377 752 721 1821
1 376 1665 661
9...

output:

Yes
00000000000000000100000000100100000110000010100011000100000000000100000001000000000001111001000010000011100000000000100100110000001000010001100111101001001000000000010001000010100100000000000001000000000010010100000010001001000000000000000000000000000000010000000100100000000000010100000100010000...

result:

ok accepted

Test #26:

score: 0
Accepted
time: 261ms
memory: 36468kb

input:

50000 66 66
196 260 1717 1519
1 65 397 397
621 686 795 815
1301 1365 1783 859
850 910 1746 1150
1431 1495 859 1189
586 650 1849 793
462 521 111 1079
1704 1763 590 699
1755 1814 1656 408
1780 1844 1879 1630
1445 1507 1488 433
695 758 284 1075
1271 1332 289 1671
1301 1365 199 331
1 65 1189 1849
1041 1...

output:

Yes
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000...

result:

ok accepted

Test #27:

score: -100
Time Limit Exceeded

input:

50000 1370 1383
263 1101 608 145
749 1622 775 1977
169 1767 1329 1459
406 588 1627 1777
156 1287 1163 961
634 718 1333 429
38 1950 1442 1135
982 1072 129 1409
1336 1395 484 961
710 1012 690 1838
276 293 1989 954
41 1793 1015 1514
730 1991 757 901
895 1185 972 1861
609 948 236 1501
285 1421 1748 630
...

output:

Yes
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result: