QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #863345 | #9745. 递增序列 | asaltfish | WA | 37ms | 7784kb | C++14 | 5.6kb | 2025-01-19 16:07:38 | 2025-01-19 16:07:38 |
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], lg[65], lg0[65], dis[200005][65];
ll bit[65];
bool all = 0;
void dfs(ll l, ll r, ll bi)
{
if (bi < 0 || all || r == l)
return;
if (dis[r][bi] - dis[l][bi] == 0)
dfs(l, r, bi - 1);
else 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), dfs(be, r, bi - 1);
}
else
{
int ch = 0;
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), dfs(be, r, bi - 1);
}
}
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;
fill(bit, bit + 65, 2);
fill(lg, lg + 65, -1);
fill(lg0, lg0 + 65, -1);
for (int i = 1;i <= n;i++)
fill(b[i], b[i] + 63, 0),fill(dis[i], dis[i] + 63, 0);
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;
// for (ll i = 62;now > 0 && i >= 0;i--)
// {
// if (b[now][i] == 0 || b[now][i] == now)
// bit[i] = 2;
// else
// {
// if ((a[now] >> i) & 1)
// {
// if (now - b[now][i] + 1ll == lg[i])
// {
// bit[i] = 0;
// while (now > 0 && ((a[now] >> i) & 1ll))
// now--;
// }
// else
// {
// flag = 1;
// break;
// }
// }
// else
// {
// if (b[lg0[i] - 1][i] == b[now][i])
// {
// bit[i] = 1;
// while (now > 0 && !((a[now] >> i) & 1ll))
// now--;
// }
// else
// {
// flag = 1;
// break;
// }
// }
// }
// }
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)
{
//ans = 0;
break;
}
}
if (now > k)
break;
}
now = k;
//now=21;
for (ll i = 1;i <= n;i++)
{
a[i] ^= now;
}
for (ll i = 2;i <= n;i++)
{
//cout<<"A"<<a[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: 5696kb
input:
1 4 17 3 2 5 16
output:
4
result:
ok single line: '4'
Test #2:
score: -100
Wrong Answer
time: 37ms
memory: 7784kb
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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
result:
wrong answer 3rd lines differ - expected: '432345564227567616', found: '0'