QOJ.ac
QOJ
QOJ is currently under a maintenance. It might be unavailable in the following a few hours.
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #818227 | #8307. Club Assignment | doyo# | WA | 27ms | 3652kb | C++20 | 1.9kb | 2024-12-17 17:47:58 | 2024-12-17 17:47:59 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void work()
{
int n; cin >> n;
vector<int> a(n + 1);
for(int i = 1; i <= n; i++) cin >> a[i];
sort(a.begin() + 1, a.end());
vector<vector<int> > v(2);
auto ok =[&] (int ans) -> bool{
v[0].clear(); v[1].clear();
bool c = 0;
v[1].push_back(1);
for(int i = 2; i < n; i++){
//cout <<(a[i] ^ a[i + 1] ) <<" " << ans <<" " << B <<"for"<<"\n";
if((a[i] ^ a[i + 1]) >= ans) v[c ^ 1].push_back(i);
else{
//cout <<"else"<< (a[i + 1] ^ B) <<" " << ans <<"\n";
if((v[c].empty() || (a[i] ^ a[v[c].back()]) >= ans) && (v[c ^ 1].empty() || (a[i + 1] ^ a[v[c ^ 1].back()]) >= ans))
v[c].push_back(i);
else
if((v[c].empty() || (a[i + 1] ^ a[v[c].back()]) >= ans) && (v[c ^ 1].empty() || (a[i] ^ a[v[c ^ 1].back()]) >= ans)){
c ^= 1;
v[c].push_back(i);
}
else return 0;
}
}
if(v[c].empty()) v[c].push_back(n);
else v[c ^ 1].push_back(n);
//cout << v[c].size() <<" " << v[c ^ 1].size()<<"\n";
return 1;
};
int L = 0, R = (1 << 30);
//R= 10;//ok(3);
while(L < R){
int mid = (L + R + 1) >> 1;
//cout << L <<" " << R <<" " <<mid <<"\n";
if(ok(mid)) L = mid;
else R = mid - 1;
}
cout << L <<"\n";
ok(L);
vector<int> ans(n + 1);
for(auto i:v[0]) ans[i] = 2;
for(auto i:v[1]) ans[i] = 1;
for(int i = 1; i <= n; i++) cout << ans[i];
cout <<"\n";
}
int main()
{
//freopen("C.out", "w", stdout);
std::cin.tie(0);
std::cin.sync_with_stdio(0);
int t=1;
std::cin>>t;
while(t--)
work();
return 0;
}
/*
1
5
1 2 3 4 5
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3652kb
input:
2 3 1 2 3 3 5 5 5
output:
3 112 0 112
result:
ok accepted
Test #2:
score: -100
Wrong Answer
time: 27ms
memory: 3596kb
input:
2000 100 7 90 64 59 9 12 72 41 72 45 35 90 65 43 81 37 49 62 42 61 12 3 30 97 3 21 43 44 18 71 3 8 70 25 55 41 43 26 80 36 11 6 36 5 57 7 35 23 72 27 73 45 2 64 86 90 47 93 54 26 7 48 63 40 1 61 35 45 11 80 90 68 20 6 22 92 57 47 37 8 84 43 51 95 20 44 89 25 65 18 79 77 5 2 85 62 63 27 62 72 100 34 ...
output:
0 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111112 0 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111112 0 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
wrong answer ans=0 instead of 1