QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#244298#7763. 左蓝右红hos_lyric#65 588ms396524kbC++147.4kb2023-11-08 22:59:012024-07-04 02:23:25

Judging History

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

  • [2024-07-04 02:23:25]
  • 评测
  • 测评结果:65
  • 用时:588ms
  • 内存:396524kb
  • [2023-11-08 22:59:01]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")

////////////////////////////////////////////////////////////////////////////////
template <unsigned M_> struct ModInt {
  static constexpr unsigned M = M_;
  unsigned x;
  constexpr ModInt() : x(0U) {}
  constexpr ModInt(unsigned x_) : x(x_ % M) {}
  constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
  constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
  constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
  ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
  ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
  ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }
  ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
  ModInt pow(long long e) const {
    if (e < 0) return inv().pow(-e);
    ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
  }
  ModInt inv() const {
    unsigned a = M, b = x; int y = 0, z = 1;
    for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
    assert(a == 1U); return ModInt(y);
  }
  ModInt operator+() const { return *this; }
  ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
  ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
  ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
  ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
  ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
  template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
  template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
  template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
  template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
  explicit operator bool() const { return x; }
  bool operator==(const ModInt &a) const { return (x == a.x); }
  bool operator!=(const ModInt &a) const { return (x != a.x); }
  friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};
////////////////////////////////////////////////////////////////////////////////

constexpr unsigned MO = 20051131;
using Mint = ModInt<MO>;


vector<int> uf;
int root(int u) {
  return (uf[u] < 0) ? u : (uf[u] = root(uf[u]));
}
bool connect(int u, int v) {
  u = root(u);
  v = root(v);
  if (u == v) return false;
  if (uf[u] > uf[v]) swap(u, v);
  uf[u] += uf[v];
  uf[v] = u;
  return true;
}

constexpr int DX[4] = {+1, 0, -1, 0};
constexpr int DY[4] = {0, +1, 0, -1};

const pair<string, Mint> NO("-1", 0);

int N;
vector<int> X0, X1, Y0, Y1;


namespace brute {
int f[4010][4010];
int meet[4010][4010];
int wall[8010][8010];

bool vis[4010][4010];
int waf;
void dfs(int x, int y) {
  vis[x][y] = true;
  for (int dir = 0; dir < 4; ++dir) {
    const int xx = x + DX[dir];
    const int yy = y + DY[dir];
    if (f[x][y] == f[xx][yy]) {
      if (!vis[xx][yy]) {
        dfs(xx, yy);
      }
    } else {
      const int w = wall[x + x + 1 + DX[dir]][y + y + 1 + DY[dir]];
      assert(~w);
      if (~waf) {
        connect(waf, w);
        connect(waf ^ 1, w ^ 1);
      } else {
        waf = w;
      }
    }
  }
}

pair<string, Mint> run() {
cerr<<"[brute::run]"<<endl;
  memset(f, 0, sizeof(f));
  for (int i = 0; i < N; ++i) {
    ++f[X0[i]][Y0[i]];
    --f[X0[i]][Y1[i]];
    --f[X1[i]][Y0[i]];
    ++f[X1[i]][Y1[i]];
  }
  for (int x = 0; x <= 2 * N; ++x) for (int y = 0; y <= 2 * N; ++y) f[x + 1][y] += f[x][y];
  for (int x = 0; x <= 2 * N; ++x) for (int y = 0; y <= 2 * N; ++y) f[x][y + 1] += f[x][y];
// for(int x=0;x<=2*N;++x)pv(f[x],f[x]+(2*N+1));
  memset(meet, 0, sizeof(meet));
  memset(wall, ~0, sizeof(wall));
  for (int i = 0; i < N; ++i) {
    { const int y = Y0[i]; for (int x = X0[i]; x < X1[i]; ++x) ++meet[x][y]; }
    { const int x = X1[i]; for (int y = Y0[i]; y < Y1[i]; ++y) ++meet[x][y]; }
    { const int y = Y1[i]; for (int x = X1[i]; x > X0[i]; --x) ++meet[x][y]; }
    { const int x = X0[i]; for (int y = Y1[i]; y > Y0[i]; --y) ++meet[x][y]; }
  }
  for (int i = 0; i < N; ++i) {
    int s = 0;
    { const int y = Y0[i]; for (int x = X0[i]; x < X1[i]; ++x) { s += (meet[x][y] - 1); wall[x + x + 1][y + y] = i << 1 | (s & 1); } }
    { const int x = X1[i]; for (int y = Y0[i]; y < Y1[i]; ++y) { s += (meet[x][y] - 1); wall[x + x][y + y + 1] = i << 1 | (s & 1); } }
    { const int y = Y1[i]; for (int x = X1[i]; x > X0[i]; --x) { s += (meet[x][y] - 1); wall[x + x - 1][y + y] = i << 1 | (s & 1); } }
    { const int x = X0[i]; for (int y = Y1[i]; y > Y0[i]; --y) { s += (meet[x][y] - 1); wall[x + x][y + y - 1] = i << 1 | (s & 1); } }
// cerr<<"i = "<<i<<": s = "<<s<<endl;
    assert(!(s & 1));
  }
// for(int x=0;x<=4*N;++x)pv(wall[x],wall[x]+(4*N+1));
  uf.assign(N << 1, -1);
  memset(vis, 0, sizeof(vis));
  for (int x = 1; x < 2 * N; ++x) for (int y = 1; y < 2 * N; ++y) if (f[x][y] & 1) {
    if (!vis[x][y]) {
      waf = -1;
      dfs(x, y);
    }
  }
  for (int i = 0; i < N; ++i) {
    if (root(i << 1) == root(i << 1 | 1)) {
      return NO;
    }
  }
  vector<int> cols(N << 1, -1);
  pair<string, Mint> ans(string(N, '?'), 1);
  for (int i = 0; i < N; ++i) {
    const int r = root(i << 1);
    if (!~cols[r]) {
      cols[r] = 0;
      cols[root(i << 1 | 1)] = 1;
      ans.second *= 2;
    }
    ans.first[i] = '0' + cols[r];
  }
  return ans;
}
}  // brute


int main() {
  for (; ~scanf("%d", &N); ) {
    X0.resize(N);
    X1.resize(N);
    Y0.resize(N);
    Y1.resize(N);
    for (int i = 0; i < N; ++i) {
      scanf("%d%d%d%d", &X0[i], &Y0[i], &X1[i], &Y1[i]);
    }
    
    pair<string, Mint> ans;
    if (N <= 2000) {
      ans = brute::run();
    } else {
      ans = make_pair(string(N, '0'), Mint(2).pow(N));
    }
    printf("%s\n", ans.first.c_str());
    printf("%u\n", ans.second.x);
  }
  return 0;
}

详细

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 0
Runtime Error

input:

200000
1 80998 2 135082
3 102065 4 124005
5 329791 6 357016
7 16209 8 249821
9 200857 10 242988
11 310613 12 330241
13 63077 14 212145
15 3305 16 172693
17 80307 18 152165
19 74160 20 277762
21 49627 22 111860
23 14498 24 175254
25 296944 26 307454
27 170816 28 292499
29 251883 30 365222
31 112774 3...

output:


result:


Subtask #2:

score: 20
Accepted

Test #2:

score: 20
Accepted
time: 27ms
memory: 395760kb

input:

10
4 3 10 8
13 10 20 16
14 11 16 14
7 17 17 20
3 1 19 15
15 4 18 13
8 2 11 7
2 12 5 18
6 5 12 6
1 9 9 19

output:

-1
0

result:

ok 2 lines

Test #3:

score: 0
Accepted
time: 7ms
memory: 395756kb

input:

9
5 8 6 12
4 5 7 15
16 1 18 2
13 6 14 16
8 17 9 18
11 7 12 11
2 3 3 4
15 9 17 10
1 13 10 14

output:

000000001
128

result:

ok 2 lines

Test #4:

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

input:

13
24 13 25 17
2 5 12 6
7 1 26 25
6 7 10 9
1 8 9 18
20 14 21 19
17 3 22 11
15 4 18 15
4 2 16 22
3 20 14 24
8 16 11 23
5 10 23 12
13 21 19 26

output:

-1
0

result:

ok 2 lines

Test #5:

score: 0
Accepted
time: 11ms
memory: 395708kb

input:

10
15 4 16 5
3 12 19 13
5 1 6 16
12 9 13 19
7 2 18 3
9 14 20 15
10 18 11 20
1 8 2 10
4 6 8 7
14 11 17 17

output:

0011000001
32

result:

ok 2 lines

Test #6:

score: 0
Accepted
time: 11ms
memory: 396048kb

input:

11
9 14 12 19
3 2 21 6
7 1 14 17
11 4 15 9
13 8 17 21
16 15 18 22
8 7 22 20
2 3 6 18
5 10 20 16
4 5 19 13
1 11 10 12

output:

-1
0

result:

ok 2 lines

Test #7:

score: 0
Accepted
time: 23ms
memory: 395744kb

input:

12
9 2 10 12
2 13 6 14
5 10 8 11
20 5 21 9
1 15 14 16
16 1 17 7
12 19 13 20
19 6 22 18
7 21 15 22
18 8 23 17
3 23 4 24
11 3 24 4

output:

000000010001
512

result:

ok 2 lines

Test #8:

score: 0
Accepted
time: 19ms
memory: 395792kb

input:

13
11 3 17 16
8 6 18 7
1 2 3 20
6 9 13 26
10 12 24 15
5 14 7 19
2 1 19 13
12 5 20 22
15 8 21 18
14 4 25 24
16 17 22 21
4 10 26 11
9 23 23 25

output:

-1
0

result:

ok 2 lines

Test #9:

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

input:

9
10 3 13 4
7 7 14 8
12 14 18 15
2 11 9 12
1 17 8 18
11 5 15 6
4 2 5 13
3 1 6 10
16 9 17 16

output:

000000001
64

result:

ok 2 lines

Test #10:

score: 0
Accepted
time: 15ms
memory: 395752kb

input:

10
14 5 16 8
10 12 13 13
6 15 17 19
3 2 11 6
19 4 20 10
2 9 5 16
7 11 18 18
12 7 15 17
1 3 8 14
4 1 9 20

output:

-1
0

result:

ok 2 lines

Test #11:

score: 0
Accepted
time: 15ms
memory: 395752kb

input:

12
5 4 6 10
14 20 22 21
19 2 20 9
7 7 12 8
15 14 18 15
1 16 21 17
3 22 8 23
23 11 24 12
9 18 10 19
4 5 11 6
16 1 17 3
2 13 13 24

output:

000000101101
256

result:

ok 2 lines

Test #12:

score: 0
Accepted
time: 19ms
memory: 395724kb

input:

9
6 5 11 15
1 16 12 18
8 9 9 17
3 12 17 13
10 3 18 11
5 2 7 4
13 8 14 10
4 1 16 14
2 6 15 7

output:

-1
0

result:

ok 2 lines

Test #13:

score: 0
Accepted
time: 15ms
memory: 395704kb

input:

11
14 7 15 10
19 3 20 4
6 16 16 17
1 19 13 20
17 2 18 11
2 5 3 13
8 6 9 18
21 1 22 21
7 9 10 14
4 8 5 15
11 12 12 22

output:

00000010001
128

result:

ok 2 lines

Test #14:

score: 0
Accepted
time: 11ms
memory: 395760kb

input:

11
20 18 21 20
1 13 4 14
7 8 19 10
2 4 16 12
18 1 22 2
13 16 15 19
9 3 10 15
3 6 5 21
8 7 17 22
11 9 14 17
6 5 12 11

output:

-1
0

result:

ok 2 lines

Test #15:

score: 0
Accepted
time: 27ms
memory: 395748kb

input:

10
11 9 12 10
14 3 15 7
19 8 20 14
8 19 9 20
6 12 7 13
1 2 2 11
13 6 16 18
3 16 10 17
4 1 5 15
17 4 18 5

output:

0000001000
512

result:

ok 2 lines

Test #16:

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

input:

10
1 1 14 14
9 2 16 3
2 10 12 11
15 4 20 13
3 7 4 20
7 8 19 16
13 6 18 17
5 5 8 19
6 12 10 15
11 9 17 18

output:

-1
0

result:

ok 2 lines

Test #17:

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

input:

12
17 11 18 24
11 19 12 20
21 16 22 18
16 17 19 21
6 12 20 13
8 9 10 10
23 5 24 6
3 1 4 14
1 4 2 7
13 8 14 15
5 22 7 23
9 2 15 3

output:

000110000000
512

result:

ok 2 lines

Subtask #3:

score: 20
Accepted

Dependency #2:

100%
Accepted

Test #18:

score: 20
Accepted
time: 11ms
memory: 395724kb

input:

8
15 6 16 9
10 1 12 2
3 8 4 10
13 13 14 15
1 11 8 12
9 4 11 5
2 3 5 16
6 7 7 14

output:

00001000
32

result:

ok 2 lines

Test #19:

score: 0
Accepted
time: 27ms
memory: 395816kb

input:

22
34 24 35 35
6 4 7 43
1 39 23 40
3 16 37 17
2 27 26 28
29 23 30 31
14 29 15 41
21 21 38 22
12 5 13 10
11 8 41 9
4 30 5 44
33 6 36 15
19 36 20 42
22 2 27 3
42 1 43 7
39 18 44 19
31 32 32 34
17 12 18 13
24 25 40 26
10 37 25 38
16 11 28 14
8 20 9 33

output:

0011100001000000001100
512

result:

ok 2 lines

Test #20:

score: 0
Accepted
time: 47ms
memory: 396048kb

input:

30
21 13 37 14
14 52 29 53
5 59 7 60
10 3 11 4
6 11 28 12
26 21 44 22
17 35 27 36
16 25 52 26
23 8 41 9
55 31 56 48
1 24 2 38
12 6 13 50
4 16 39 17
3 41 54 42
22 15 57 18
49 57 53 58
38 20 51 23
15 33 43 34
47 43 48 44
19 27 46 28
32 47 33 56
42 51 58 54
59 2 60 30
30 7 31 29
18 32 40 37
8 40 45 45
...

output:

-1
0

result:

ok 2 lines

Test #21:

score: 0
Accepted
time: 19ms
memory: 395788kb

input:

40
8 9 9 66
11 74 12 75
55 20 57 21
51 11 52 63
70 4 71 19
59 3 60 55
49 12 50 80
3 34 65 35
67 49 68 50
28 1 75 2
34 15 48 16
1 10 2 22
29 23 35 24
46 58 47 76
62 65 63 78
7 14 10 61
23 37 40 38
15 48 16 64
53 69 72 70
58 13 61 26
18 72 21 73
25 28 69 29
13 5 22 6
31 32 32 79
19 46 80 47
43 25 44 3...

output:

-1
0

result:

ok 2 lines

Test #22:

score: 0
Accepted
time: 32ms
memory: 395724kb

input:

53
10 11 98 12
25 54 33 55
23 4 40 5
65 16 66 21
7 44 83 45
3 36 4 88
11 70 39 71
12 47 102 48
56 77 81 78
82 74 97 75
60 1 61 105
91 2 94 3
43 83 44 99
92 25 93 31
104 98 105 102
57 24 58 43
46 72 88 73
16 32 17 90
32 13 45 14
22 66 87 67
51 8 52 63
99 61 100 79
53 28 54 56
19 103 96 104
1 51 2 58
...

output:

-1
0

result:

ok 2 lines

Test #23:

score: 0
Accepted
time: 16ms
memory: 395764kb

input:

196
102 329 241 330
26 69 27 70
77 230 78 256
135 302 136 311
47 125 174 126
94 385 310 386
73 305 164 306
277 20 278 102
237 28 238 168
207 59 208 244
173 7 319 8
369 37 370 215
203 277 267 278
81 24 82 124
57 353 134 354
263 95 264 355
74 185 192 186
152 33 375 34
161 167 162 207
177 381 248 382
1...

output:

0011000111010101001000100001010000010000001110111001111010000001101001100010010000000111000010111101010010000000111100011010011100101000100010001100000011110100111110100100100110000000011111011011
6955471

result:

ok 2 lines

Test #24:

score: 0
Accepted
time: 24ms
memory: 395760kb

input:

196
153 175 314 176
335 53 336 273
283 10 284 19
103 87 383 88
140 251 200 252
345 195 346 226
285 126 286 181
24 55 75 56
63 383 295 384
61 96 62 235
239 381 244 382
151 79 184 80
7 159 172 160
143 391 217 392
169 94 170 327
77 178 78 197
175 91 176 275
195 183 196 264
281 64 282 333
303 190 304 24...

output:

0110011001000011111101000010100100101001111011100101001100110010010001110111101011000000101000001000101011100010100000011101011011100001110000101001100000010111100000110001111110010100001100000110
524288

result:

ok 2 lines

Test #25:

score: 0
Accepted
time: 31ms
memory: 395788kb

input:

196
161 83 191 84
355 162 356 225
333 91 334 133
239 50 240 98
57 23 189 24
47 40 48 380
33 389 156 390
116 307 218 308
15 134 16 275
93 297 129 298
317 191 318 276
325 107 326 370
371 149 372 375
302 357 379 358
125 159 126 161
85 285 192 286
21 76 22 87
227 33 228 208
6 29 9 30
117 4 118 6
199 129...

output:

0111010010111000110000110011100101101101001111010001111100001011010001001110110100011101100100011111100101001010110000101100100000101010001010010100100001011100100001000000110100111010000101001010
524288

result:

ok 2 lines

Test #26:

score: 0
Accepted
time: 19ms
memory: 396036kb

input:

198
184 163 199 164
137 7 138 366
115 66 116 272
213 349 214 372
82 155 128 156
3 54 4 283
87 85 145 86
225 37 226 235
108 35 227 36
259 333 370 334
35 355 371 356
185 47 186 376
11 21 27 22
349 11 396 12
139 59 140 134
5 95 6 186
195 89 196 298
119 374 120 387
51 30 52 147
179 263 180 383
63 75 327...

output:

011100010001001011110000000101010011100110111101110101010010100001000000010110101000001001111000110001111100011111101101000100111100000010000010101100001111110101001011110101000001010101010000001001
524288

result:

ok 2 lines

Test #27:

score: 0
Accepted
time: 19ms
memory: 396032kb

input:

197
307 29 308 37
19 235 138 236
263 263 331 264
133 327 217 328
66 381 280 382
319 295 320 352
220 99 260 100
169 39 170 84
41 73 346 74
90 63 303 64
264 289 373 290
13 8 14 334
27 87 213 88
327 129 328 320
42 115 172 116
145 7 146 207
135 94 136 390
205 292 206 301
233 61 361 62
203 150 204 341
92...

output:

00000101000101011001011101101100111101010000111011101100011010101000100010001110100111101010111001001001111111110001110010011001011000001010000101000101110001110000100110011011110000100101101000010
4194304

result:

ok 2 lines

Test #28:

score: 0
Accepted
time: 23ms
memory: 396140kb

input:

200
63 43 202 251
3 260 226 347
142 201 361 289
52 36 300 46
140 115 228 238
2 236 276 359
308 154 330 373
8 172 119 187
58 161 355 371
68 213 283 349
82 110 205 296
93 90 193 94
64 169 305 252
208 147 329 382
345 156 395 357
190 327 372 344
321 145 354 395
179 140 340 378
22 286 186 368
70 143 250 ...

output:

-1
0

result:

ok 2 lines

Test #29:

score: 0
Accepted
time: 27ms
memory: 395780kb

input:

197
1 1 198 198
2 2 199 199
3 3 200 200
4 4 201 201
5 5 202 202
6 6 203 203
7 7 204 204
8 8 205 205
9 9 206 206
10 10 207 207
11 11 208 208
12 12 209 209
13 13 210 210
14 14 211 211
15 15 212 212
16 16 213 213
17 17 214 214
18 18 215 215
19 19 216 216
20 20 217 217
21 21 218 218
22 22 219 219
23 23 ...

output:

00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
2

result:

ok 2 lines

Test #30:

score: 0
Accepted
time: 24ms
memory: 395720kb

input:

197
1 197 394 198
2 196 393 199
3 195 392 200
4 194 391 201
5 193 390 202
6 192 389 203
7 191 388 204
8 190 387 205
9 189 386 206
10 188 385 207
11 187 384 208
12 186 383 209
13 185 382 210
14 184 381 211
15 183 380 212
16 182 379 213
17 181 378 214
18 180 377 215
19 179 376 216
20 178 375 217
21 17...

output:

01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010
2

result:

ok 2 lines

Subtask #4:

score: 25
Accepted

Dependency #3:

100%
Accepted

Test #31:

score: 25
Accepted
time: 24ms
memory: 395700kb

input:

10
7 6 12 7
16 11 18 12
13 3 19 4
3 14 5 15
1 2 11 5
6 17 10 18
4 16 17 19
8 13 9 20
14 1 15 8
2 9 20 10

output:

0000000110
128

result:

ok 2 lines

Test #32:

score: 0
Accepted
time: 20ms
memory: 395752kb

input:

18
1 32 17 33
11 20 33 21
5 2 6 34
19 12 21 13
12 22 18 23
29 3 30 24
27 9 28 10
22 17 23 35
3 8 20 11
15 26 34 27
13 1 14 16
24 19 25 31
4 5 31 6
7 18 8 36
2 7 16 14
35 4 36 15
26 28 32 29
9 25 10 30

output:

001001010011010000
128

result:

ok 2 lines

Test #33:

score: 0
Accepted
time: 34ms
memory: 396048kb

input:

31
26 55 56 56
29 35 50 36
51 4 52 33
21 54 22 60
40 3 41 50
16 61 44 62
8 1 9 34
35 32 36 44
24 23 25 51
48 27 49 43
57 26 58 41
3 17 55 18
32 58 53 59
30 19 31 21
11 2 12 15
14 39 27 40
4 30 38 31
33 22 34 46
13 8 15 9
17 24 60 25
5 48 47 49
61 7 62 20
28 52 43 53
1 5 2 12
20 6 23 16
18 28 19 42
3...

output:

-1
0

result:

ok 2 lines

Test #34:

score: 0
Accepted
time: 20ms
memory: 395792kb

input:

42
8 40 9 46
62 3 77 4
37 15 38 21
57 24 58 67
26 45 27 50
40 19 55 20
13 66 14 70
21 51 83 52
42 9 43 10
12 41 15 82
33 8 34 72
2 48 46 49
29 17 49 18
35 42 36 44
79 26 80 64
24 5 44 6
16 16 17 77
7 14 10 25
64 43 65 81
75 7 76 80
70 83 81 84
50 11 61 12
3 68 53 69
11 59 18 65
66 47 67 71
71 32 72 ...

output:

000000010001100000000011001101110001010110
32768

result:

ok 2 lines

Test #35:

score: 0
Accepted
time: 12ms
memory: 395764kb

input:

52
54 36 55 51
23 77 48 78
24 101 99 102
92 6 93 93
53 8 56 104
21 99 57 100
44 44 62 45
10 80 104 81
15 17 16 26
27 75 32 76
28 74 97 79
47 4 83 5
78 27 79 64
7 2 65 3
13 16 14 25
85 70 86 73
73 10 74 65
11 24 12 85
9 60 88 61
66 11 67 19
6 21 98 22
20 67 36 68
71 38 94 39
40 1 41 12
37 53 38 103
5...

output:

-1
0

result:

ok 2 lines

Test #36:

score: 0
Accepted
time: 299ms
memory: 396060kb

input:

1999
3457 1145 3458 3805
907 29 2798 30
3527 3753 3528 3968
2453 2197 2959 2198
543 2921 2366 2922
3217 2697 3425 2698
320 1471 2051 1472
1055 683 1056 1473
2695 1491 2696 3364
3099 1022 3100 1544
2198 2415 3137 2416
204 2155 1320 2156
3933 244 3934 3063
2923 173 3668 174
87 1710 88 2403
1047 1608 1...

output:

010111100011010000000000011010110011001101101001110000101100110100010100110101000001100011100001001011101010001101111111100100010001111111111010010110001010011111101111100000000110010110110001110011010101111111101110001101001111001110101010000011110110100010111010011001011011101001001110001101010011...

result:

ok 2 lines

Test #37:

score: 0
Accepted
time: 311ms
memory: 395972kb

input:

1998
3015 2485 3016 3721
958 3537 1331 3538
937 438 938 3117
3101 1910 3102 2144
302 3015 3361 3016
971 678 972 3109
3827 2861 3891 2862
95 1872 96 2846
615 2991 2114 2992
2527 2033 2528 2401
1124 3885 3753 3886
1665 2514 1666 3028
418 1053 3495 1054
1943 415 3187 416
3611 58 3612 2210
1596 655 2227...

output:

010010101010110101010011000010000010100011100110000101110000010010111111011010001000100111000110000001010000010101011010100011100000110110011010110111100000001111001010011011001010011101101000000000010100011011001011101100000100111001110111010101001100111100101011101000111101011010001011100011011010...

result:

ok 2 lines

Test #38:

score: 0
Accepted
time: 304ms
memory: 396048kb

input:

1998
3943 98 3944 943
3638 3681 3985 3682
2681 537 3633 538
1048 977 3821 978
437 871 689 872
1032 3359 2991 3360
1277 2935 2405 2936
1611 2387 3295 2388
1615 2789 3533 2790
1805 476 1806 788
3393 1831 3394 2367
588 2009 743 2010
3450 647 3828 648
578 2897 2053 2898
2945 207 3734 208
165 1269 2206 1...

output:

011111111001111101010100000101010010111100110000101110111101000000001000011001000011111111000111001100000000000010111100111001100100010011001111000011111111001001010001001010010110001100110011010100110010010100111111110011111110100010001011111111100101001000101011000110110100011000110001101000010010...

result:

ok 2 lines

Test #39:

score: 0
Accepted
time: 310ms
memory: 395964kb

input:

1999
1847 331 1848 3924
3347 624 3348 1034
513 1167 2081 1168
3233 1584 3234 1748
247 3897 2996 3898
1512 3575 2252 3576
1910 3041 3254 3042
1046 3549 3059 3550
930 1313 1713 1314
2659 64 2660 360
567 3083 2053 3084
1875 865 2828 866
3405 2974 3406 3251
1380 147 2173 148
617 2175 2393 2176
971 1095 ...

output:

001011111011011111011110110011100101100011000001010011001010001011010110110000011100010110010000011110111000110001110110010001000001101000101010111011000110101111100100101100011000110011101010111100011010010001101101001111001100000100010001011010101000101000101100111110111010000001100111100011110101...

result:

ok 2 lines

Test #40:

score: 0
Accepted
time: 266ms
memory: 396076kb

input:

1996
908 1483 3742 1484
1009 1171 1010 3642
897 1770 898 2144
1259 310 1260 1514
2973 488 2974 3184
2681 1335 2812 1336
2136 3161 3563 3162
1032 3631 3528 3632
439 2086 440 2396
157 3619 3974 3620
2109 419 2110 2292
1741 1788 1742 3924
3395 2173 3396 2830
2823 348 2824 672
3533 1207 3534 3302
711 17...

output:

011110001011111011001100110010010000010000111010110101101100111101000100111101010101001111101000000111001010000101000001100101110111110110011010100100110110000011111011101100010100111011110011111001100110000001011011100110000100011100011001111111110110110100011010101100000001111001101000000000100100...

result:

ok 2 lines

Test #41:

score: 0
Accepted
time: 588ms
memory: 396524kb

input:

1999
731 943 1061 2908
2186 1335 3196 3689
1818 933 3662 3139
908 1997 2991 2033
870 1918 3645 3815
1000 3594 3086 3791
1592 1342 1992 2491
1588 65 1857 834
3049 171 3543 3428
1021 1955 3219 2924
2459 408 2936 684
329 2674 1372 3399
2293 160 2301 1424
3015 1826 3530 3192
1803 2103 3763 2819
1828 117...

output:

-1
0

result:

ok 2 lines

Test #42:

score: 0
Accepted
time: 587ms
memory: 396120kb

input:

1998
1 1 1999 1999
2 2 2000 2000
3 3 2001 2001
4 4 2002 2002
5 5 2003 2003
6 6 2004 2004
7 7 2005 2005
8 8 2006 2006
9 9 2007 2007
10 10 2008 2008
11 11 2009 2009
12 12 2010 2010
13 13 2011 2011
14 14 2012 2012
15 15 2013 2013
16 16 2014 2014
17 17 2015 2015
18 18 2016 2016
19 19 2017 2017
20 20 201...

output:

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok 2 lines

Test #43:

score: 0
Accepted
time: 466ms
memory: 395812kb

input:

1998
1 1998 3996 1999
2 1997 3995 2000
3 1996 3994 2001
4 1995 3993 2002
5 1994 3992 2003
6 1993 3991 2004
7 1992 3990 2005
8 1991 3989 2006
9 1990 3988 2007
10 1989 3987 2008
11 1988 3986 2009
12 1987 3985 2010
13 1986 3984 2011
14 1985 3983 2012
15 1984 3982 2013
16 1983 3981 2014
17 1982 3980 201...

output:

010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101...

result:

ok 2 lines

Subtask #5:

score: 0
Skipped

Dependency #1:

0%