QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #579495 | #9221. Missing Boundaries | Fiatiustitia# | WA | 199ms | 34620kb | C++20 | 3.3kb | 2024-09-21 14:16:47 | 2024-09-21 14:16:48 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
pair<int, int> a[N];
int f[N][2];
int MAX, MIN;
void solve()
{
int n, m;
MAX = MIN = 0;
cin >> n >> m;
map<int, vector<pair<int, int>>> mp;
int cnt = 0;
a[0].first = 0;
a[0].second = 0;
for (int i = 1; i <= n; i++)
cin >> a[i].first >> a[i].second, cnt += (a[i].first == -1 && a[i].second == -1), f[i][0] = a[i].first, f[i][1] = a[i].second;
for (int i = 1; i <= n; i++)
{
if (a[i].first != -1)
mp[a[i].first].push_back(make_pair(i, 0));
if (a[i].second != -1)
mp[a[i].second].push_back(make_pair(i, 1));
}
if (n > m)
{
cout << "NIE\n";
return;
}
if (mp.size() == 0)
{
cout << "TAK\n";
return;
}
auto [pp, v1] = *(--mp.end());
int ttp = 0;
for (auto x : v1)
ttp = x.second;
if (ttp && pp != m)
{
// cnt--;
MIN++;
MAX += (m - pp);
// if (cnt < 0)
// {
// cout << "NIE\n";
// return;
// }
}
for (auto [_, v] : mp)
if (v.size() > 2 || v.size() == 2 && v[0].first != v[1].first)
{
cout << "NIE\n";
return;
}
pair<int, int> pre = make_pair(0, 1);
for (auto [pos, v] : mp)
{
for (auto [x, y] : v)
{
auto [x1, y1] = pre;
if (y && y1) // RR
{
if (f[x][y ^ 1] < f[x1][y1] && f[x][y ^ 1] != -1)
{
cout << "NIE\n";
return;
}
// if (pos - f[x1][y1] <= 0)
// {
// cout << "NIE\n";
// return;
// }
}
else if (y && !y1)
{ // LR
if (f[x1][y1 ^ 1] > pos)
{
cout << "NIE\n";
return;
}
// if (pos - f[x1][y1] <= 2)
// {
// cout << "NIE\n";
// return;
// }
}
else if (!y && y1) // RL
{
if (pos - f[x1][y1] > 1)
{
// cnt--;
MIN++;
MAX += (pos - 1 - f[x1][y1]);
// if (cnt < 0)
// {
// cout << "NIE\n";
// return;
// }
}
}
else
{ // LL
if (f[x1][y1 ^ 1] > pos)
{
cout << "NIE\n";
return;
}
}
pre = make_pair(x, y);
}
}
cout << ((MIN <= cnt && MAX >= cnt) ? "TAK\n" : "NIE\n");
}
int main()
{
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
auto _ = clock();
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--)
solve();
return 0;
}
/*
3
4 51
1 -1
11 50
-1 -1
-1 10
3 2
-1 -1
-1 -1
-1 -1
2 3
1 2
2 3
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5604kb
input:
3 4 51 1 -1 11 50 -1 -1 -1 10 3 2 -1 -1 -1 -1 -1 -1 2 3 1 2 2 3
output:
TAK NIE NIE
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 199ms
memory: 34620kb
input:
1 200000 1000000000 490669427 -1 224278942 224287156 821104480 -1 861696576 861702036 807438935 807440055 574078002 574083717 465630141 -1 195378188 -1 -1 13500961 -1 977536179 92893115 -1 -1 661145418 -1 215804863 -1 685338515 544348999 -1 465532902 -1 130346949 -1 -1 526666304 635604584 635605404 ...
output:
TAK
result:
ok single line: 'TAK'
Test #3:
score: 0
Accepted
time: 1ms
memory: 5668kb
input:
3 4 51 1 -1 11 50 -1 -1 -1 10 3 2 -1 -1 -1 -1 -1 -1 2 3 1 2 2 3
output:
TAK NIE NIE
result:
ok 3 lines
Test #4:
score: 0
Accepted
time: 151ms
memory: 32996kb
input:
1 197838 400000 34167 34169 352180 -1 235963 -1 -1 -1 160401 160405 347288 -1 270353 270354 214502 214504 183243 183245 -1 -1 -1 36193 -1 -1 -1 17557 273498 273500 269137 -1 395099 395100 285515 285518 -1 -1 71041 71042 324060 -1 -1 385151 -1 379645 -1 -1 -1 185142 -1 191584 89259 89261 328347 32834...
output:
TAK
result:
ok single line: 'TAK'
Test #5:
score: 0
Accepted
time: 77ms
memory: 20256kb
input:
2 97340 150000 -1 101927 105937 -1 -1 107253 -1 47307 110550 -1 84061 84062 125176 125177 -1 15915 29617 -1 -1 -1 -1 43147 115958 -1 101807 101808 24866 -1 66826 66828 -1 31640 -1 5610 1281 1284 -1 -1 -1 -1 -1 73973 -1 2945 29064 -1 30653 -1 -1 63714 -1 -1 141389 141390 -1 27465 57358 -1 47388 47389...
output:
NIE NIE
result:
ok 2 lines
Test #6:
score: 0
Accepted
time: 76ms
memory: 11528kb
input:
4 50000 50000 11702 -1 -1 3148 30364 -1 48876 -1 -1 10739 -1 44459 11634 -1 39348 -1 38829 -1 16182 -1 37933 -1 35295 -1 43280 -1 37745 -1 -1 40076 358 -1 14043 -1 13975 -1 41942 -1 -1 13182 14780 -1 -1 14663 3998 -1 -1 24474 -1 6583 -1 9620 -1 37944 12103 -1 8307 -1 45760 -1 -1 2924 25441 -1 -1 194...
output:
TAK NIE NIE NIE
result:
ok 4 lines
Test #7:
score: 0
Accepted
time: 159ms
memory: 33312kb
input:
1 197884 400000 299276 299281 340251 -1 -1 350350 315166 -1 103436 103438 164740 164742 237539 -1 383864 -1 205194 -1 -1 -1 69029 69030 -1 -1 231837 231838 35835 35837 387743 -1 125024 -1 -1 -1 -1 -1 -1 -1 -1 283202 94212 94213 219223 219224 -1 -1 -1 139549 260062 -1 387170 387173 -1 328548 -1 -1 -1...
output:
NIE
result:
ok single line: 'NIE'
Test #8:
score: 0
Accepted
time: 74ms
memory: 16644kb
input:
2 97399 150000 -1 -1 97327 97328 94010 94011 72148 -1 -1 28604 -1 -1 139279 -1 -1 -1 67725 67726 93094 -1 -1 10828 37742 -1 69460 -1 -1 -1 -1 -1 80200 80202 126739 -1 131808 131810 -1 13390 -1 -1 141120 141121 127549 -1 -1 -1 -1 -1 66081 -1 100916 100918 -1 -1 25966 -1 47034 47036 101842 -1 -1 -1 -1...
output:
NIE NIE
result:
ok 2 lines
Test #9:
score: 0
Accepted
time: 88ms
memory: 13564kb
input:
4 50000 1000000000 218423429 -1 593054951 -1 345188314 -1 839833278 -1 -1 253444951 -1 532444671 -1 866445317 -1 476576639 -1 950754898 -1 735671066 71213664 -1 -1 363816338 -1 451093114 487349837 -1 -1 987865563 672130428 -1 -1 313206174 -1 311825154 -1 209018142 836501057 -1 -1 387134322 -1 939803...
output:
NIE NIE TAK NIE
result:
ok 4 lines
Test #10:
score: 0
Accepted
time: 72ms
memory: 16904kb
input:
2 97206 150000 41741 41742 -1 -1 29609 29610 -1 -1 94303 94305 67375 -1 84593 84597 -1 -1 97516 97517 -1 -1 110718 -1 129532 129533 -1 74454 -1 145160 118122 -1 -1 -1 -1 131430 -1 -1 77307 -1 -1 -1 35606 35607 -1 -1 77284 77286 84225 -1 82910 82911 55414 55418 -1 145197 -1 -1 -1 41997 41620 41621 16...
output:
NIE NIE
result:
ok 2 lines
Test #11:
score: 0
Accepted
time: 140ms
memory: 32308kb
input:
1 200000 1000000000 -1 -1 709526131 709534689 820094363 820094954 -1 558894593 253939639 253940489 755238142 -1 356834271 -1 720874328 -1 -1 797706622 -1 -1 877671011 877674221 9379767 9379808 152611373 -1 -1 584054839 -1 28003439 137254045 -1 -1 -1 -1 -1 -1 371861650 -1 -1 898245136 -1 610262985 61...
output:
TAK
result:
ok single line: 'TAK'
Test #12:
score: -100
Wrong Answer
time: 36ms
memory: 5672kb
input:
30000 6 9 -1 -1 -1 5 7 8 -1 2 -1 -1 3 -1 8 10 -1 -1 2 4 8 -1 -1 -1 3 6 2 10 -1 -1 -1 -1 5 10 7 -1 7 -1 -1 -1 -1 -1 -1 10 5 7 4 5 -1 -1 4 -1 -1 7 -1 4 9 10 -1 -1 -1 -1 8 9 9 -1 5 -1 -1 -1 -1 2 4 9 3 7 3 5 5 -1 3 3 -1 3 10 10 5 -1 1 3 -1 6 4 7 -1 5 2 -1 6 8 -1 9 7 -1 2 -1 1 6 3 -1 9 9 5 8 -1 4 1 3 8 9...
output:
TAK NIE NIE NIE NIE NIE NIE NIE NIE NIE TAK NIE NIE NIE NIE NIE NIE NIE TAK TAK TAK NIE NIE NIE NIE NIE NIE NIE TAK TAK NIE TAK NIE NIE NIE TAK NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE TAK NIE NIE NIE NIE NIE NIE NIE TAK NIE NIE NIE NIE NIE NIE TAK NIE TAK NIE NIE TAK TAK NIE NIE TAK TAK NIE ...
result:
wrong answer 42nd lines differ - expected: 'TAK', found: 'NIE'