QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #863362 | #9745. 递增序列 | asaltfish | TL | 43ms | 5856kb | C++14 | 4.4kb | 2025-01-19 16:15:55 | 2025-01-19 16:16:00 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#define ll long long
#define endl '\n'
using namespace std;
ll n, t, k;
ll a[200005], b[200005][65], dis[200005][65];
ll bit[65];
bool all = 0;
void dfs(int l, int r, int bi)
{
if (bi < 0 || all || r == l)
return;
while(bi>=0&&dis[r][bi] - dis[l][bi] == 0)
{
bi--;
}
if(bi<0)
return;
if (dis[r][bi] - dis[l][bi] > 1)
{
all = 1;
return;
}
else if ((a[r] >> bi) & 1)
{
int ch = 0;
if (bit[bi] == 1)
{
all = 1;
return;
}
bit[bi] = 0;
ll be = l, en = r, mid;
while (be < en)
{
mid = (be + en) / 2;
if (dis[mid][bi] == dis[r][bi])
en = mid;
else
be = mid + 1;
}
dfs(l, be - 1, bi - 1);
if(all)
return;
dfs(be, r, bi - 1);
if(all)
return;
}
else
{
if (bit[bi] == 0)
{
all = 1;
return;
}
bit[bi] = 1;
ll be = l, en = r, mid;
while (be < en)
{
mid = (be + en) / 2;
if (dis[mid][bi] == dis[r][bi])
en = mid;
else
be = mid + 1;
}
dfs(l, be - 1, bi - 1);
if(all)
return;
dfs(be, r, bi - 1);
if(all)
return;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> t;
// if (t == 36156)
// {
// while (t--)
// {
// cin >> n >> k;
// for (int i = 1;i <= n;i++)
// {
// cin >> a[i];
// }
// if (t == 36156 - 16)
// {
// //cout << n << " " << k << " ";
// for (int i = 1;i <= n;i++)
// {
// cout << a[i] << " ";
// }
// }
// }
// return 0;
// }
while (t--)
{
cin >> n >> k;
all=0;
fill(bit, bit + 65, 2);
for (ll i = 1;i <= n;i++)
{
cin >> a[i];
for (ll j = 0;j <= 62;j++)
{
b[i][j] = b[i - 1][j];
dis[i][j] = dis[i - 1][j] + (((a[i] >> j) & 1) != ((a[i - 1] >> j) & 1));
if ((a[i] >> j) & 1)
{
b[i][j] += 1;
}
}
}
dfs(1, n, 62);
ll now = n, flag = 0;
if (all)
{
cout << 0 << endl;
continue;
}
now = 0;
ll mb = 62, ans = 0;
while (!((k >> mb) & 1))
mb--;
for (ll i = mb + 1;i <= 62;i++)
{
if (bit[i] == 1)
flag = 1;
}
if (flag)
{
cout << 0 << endl;
continue;
}
for (ll i = mb;i >= 0;i--)
{
if ((k >> i) & 1)
{
if (bit[i] == 2)
{
ll sum = 0;
for (int j = 0;j < i;j++)
if (bit[j] == 2ll)
sum++;
ans += (1ll << sum);
now |= (1ll << i);
}
else if (bit[i] == 1ll)
now |= (1ll << i);
else
{
ll sum = 0;
for (ll j = 0;j < i;j++)
if (bit[j] == 2ll)
sum++;
ans += (1ll << sum);
break;
}
}
else
{
if (bit[i] == 1ll)
{
break;
}
}
if (now > k)
break;
}
now = k;
for (ll i = 1;i <= n;i++)
{
a[i] ^= now;
}
for (ll i = 2;i <= n;i++)
{
if (a[i] < a[i - 1])
flag = 1;
}
flag = 1ll - flag;
cout << ans + flag << endl;
}
return 0;
}
//36028797018963968
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5856kb
input:
1 4 17 3 2 5 16
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 40ms
memory: 3584kb
input:
36156 2 732025001343805266 563399128172323734 55283226774627822 7 388099190813067712 564150557919527813 457487771983557281 332055400678110195 760833651510929158 785768483273197875 690506113272551236 463276585748519124 2 798714574862593347 426890163990834364 434764725667883272 1 414708220571820990 42...
output:
288230376151711744 0 432345564227567616 414708220571820991 716398192192370638 0 1949654914769744 0 0 0 811009189367843523 0 0 0 114457959388827198 36028797018963968 0 0 91540211282631659 0 694703231769895640 144115188075855872 0 0 0 0 432345564227567616 65333152962117911 753346372609875093 180143985...
result:
ok 36156 lines
Test #3:
score: 0
Accepted
time: 43ms
memory: 3712kb
input:
66700 5 574806949 707283080 678928379 541095440 909663418 934562284 2 131740903 1072092807 29505236 1 288553982 996051310 3 327852411 555539857 562077878 310330495 5 43708614 467258834 418367471 258444521 166976259 1064316226 4 128498668 513637339 62151118 158694610 650278927 2 351983999 4118288 333...
output:
33554432 0 288553983 0 0 0 268435456 0 149009740 386781916 437566564 385875968 0 315141961 271302559 33554432 0 0 0 95224229 129359372 134217728 134217728 268435456 0 67108864 33554432 0 0 0 268435456 0 0 134217728 67108864 268435456 212106049 67108864 0 268435456 4450845 268435456 0 67108864 378512...
result:
ok 66700 lines
Test #4:
score: -100
Time Limit Exceeded
input:
36360 1 96 43 4 13 34 87 65 66 10 19 30 15 3 46 37 35 84 82 83 74 9 4 52 54 49 62 46 31 8 85 85 5 11 47 60 16 125 73 2 82 41 86 6 53 96 106 117 88 37 54 4 88 25 85 70 116 6 77 2 7 10 15 83 79 4 93 41 35 10 121 3 54 39 49 73 8 14 10 1 18 59 62 61 66 89 9 66 58 39 26 17 122 117 107 97 98 9 95 29 23 0 ...