QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #216519 | #6667. Prosjek | rbtree | 0 | 0ms | 0kb | C++14 | 2.2kb | 2023-10-15 19:21:07 | 2023-10-15 19:21:08 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
int ctz(ll x){return __builtin_ctzll(x);}
int get(ll x){return (x>>1)&1;}
void Do(ll &x,ll y){printf("%lld %lld\n",x,y);x=(x+y)/2;}
void simple(const vl &A)
{
vl vec[2];
for(ll x:A) vec[get(x)].push_back(x);
for(ll x,y;vec[0].size()>1 || vec[1].size()>1;)
{
int k=(vec[1].size()<=1);
x=vec[k].back();vec[k].pop_back();
y=vec[k].back();vec[k].pop_back();
Do(x,y);vec[get(x)].push_back(x);
}
if(!vec[0].empty() && !vec[1].empty()) Do(vec[0][0],vec[1][0]);
}
bool check(vl &A,vl &spc)
{
int n=A.size(),p=0,k=0;
for(int i=1;i<n;i++)
if(A[0]!=A[i] && (!p || ctz(A[0]^A[i])<k)) p=i,k=ctz(A[0]^A[i]);
if(!p || n<k+1) return false;
ll x=A[0],y=A[p];
A.erase(A.begin()+p);A.erase(A.begin());
for(int i=1;i<k;i++) Do(x,y),y=A.back(),A.pop_back();
assert(get(x)!=get(y));spc={x,y};
return true;
}
int main()
{
int T;
cin>>T;
while(T--)
{
int n;ll x;
scanf("%d",&n);
vl vec[2];
for(int i=1;i<=n;i++) scanf("%lld",&x),vec[x&1].push_back(x);
if(vec[0].empty()) simple(vec[1]);
else if(vec[1].empty()) simple(vec[0]);
else
{
vl spc;
if(!check(vec[0],spc) && !check(vec[1],spc)) puts("-1");
else
{
for(ll x,y;vec[0].size()>1 || vec[1].size()>1;)
{
int k=(vec[1].size()>1);
x=vec[k].back();vec[k].pop_back();
y=vec[k].back();vec[k].pop_back();
Do(x,y);vec[x&1].push_back(x);
}
if(spc[0]&1) swap(vec[0],vec[1]);
if(!vec[0].empty() && !vec[1].empty())
{
if(get(spc[0])!=get(vec[0][0])) swap(spc[0],spc[1]);
if(spc[0]%8==vec[0][0]%8) Do(spc[0],vec[0][0]),Do(spc[0],spc[1]),Do(spc[0],vec[1][0]);
else if((((spc[0]+spc[1])/2+vec[1][0])/2+vec[0][0])%2==0) Do(spc[1],spc[0]),Do(spc[1],vec[1][0]),Do(spc[1],vec[0][0]);
else Do(spc[1],vec[0][0]),Do(spc[1],vec[1][0]),Do(spc[1],spc[0]);
}
else if(!vec[0].empty())
{
if(get(spc[0])!=get(vec[0][0])) swap(spc[0],spc[1]);
Do(spc[0],vec[0][0]);Do(spc[0],spc[1]);
}
else if(!vec[1].empty()) Do(spc[0],spc[1]),Do(spc[0],vec[1][0]);
else Do(spc[0],spc[1]);
}
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
input:
99 4 739880851158065302 19206582949872932 883064254701115295 222072661880779376 7 148399819461615003 209088712310207988 53191076581680214 445068618251612752 230505279594622109 115754892157516718 804173775829453588 2 77979357045500669 41693388829622019 3 341612949433488278 609808714829036935 19994167...
output:
result:
Subtask #2:
score: 0
Runtime Error
Test #16:
score: 0
Runtime Error
input:
100 3 3 3 2 3 4 1 1 4 1 3 4 4 6 4 4 2 3 1 2 4 0 2 1 4 3 0 2 0 7 3 3 1 1 3 4 0 2 0 4 4 1 4 2 3 7 4 0 0 3 2 3 4 4 4 2 0 3 7 0 2 2 1 4 2 4 7 3 0 3 1 2 0 3 4 4 3 1 4 6 2 3 0 1 3 4 5 1 4 0 3 4 5 4 2 0 4 2 3 0 1 2 6 4 1 4 2 0 4 7 4 2 4 3 1 3 1 4 1 4 4 0 2 1 1 6 0 3 3 0 0 4 7 4 3 0 3 3 3 4 4 4 1 1 3 6 2 0 ...
output:
-1 -1 4 4 1 3 2 4 1 3 2 2 2 4 4 2 3 3 2 4 3 1 2 0 2 33 17 0 8 0 4 49 26 0 13 0 2 0 1 2 1 0 0 49 24 0 12 0 6 6 2 6 4 6 5 0 2 5 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:
Subtask #3:
score: 0
Runtime Error
Test #34:
score: 0
Runtime Error
input:
100000 5 846784256447769304 457696478728961702 128469521648960690 597630796847754190 104256763714529164 5 658897822238868978 472135077337628566 399538027669313322 622703684108675696 425723088635325654 5 917704960887390986 140817562615382054 877934664521057998 782212806618666818 616380973421914538 8 ...
output:
104256763714529164 846784256447769304 33 0 16 0 8 0 4 0 104256763714529164 597630796847754190 350943780281141677 128469521648960690 457696478728961702 846784256447769304 81 0 40 475520510081149234 237760255040574637 597630796847754190 417695525944164413 94652153458704 0 49 24 0 12 94652153458704 946...
result:
Subtask #4:
score: 0
Runtime Error
Test #46:
score: 0
Runtime Error
input:
100 211957 911918942087402387 344230223346742784 16289402153237664 528890583619159010 886281719684850237 865484734102017297 321851390502278959 754268375474197153 237414161302130571 135637002716682378 824412491959977735 162505521049217610 246319278060116103 666703181591704279 650875500699154233 96397...
output:
532418085391726079 759554573156793027 645986329274259553 553185893931599463 591082823267833997 750673279799819289 670878051533826643 708237805751519827 689557928642673235 274990826677686423 482274377660179829 749387671911821385 615831024786000607 596300148468541635 606065586627271121 187498294172452...