QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#151069#6667. Prosjekblackyuki0 4ms3544kbC++143.9kb2023-08-26 15:16:102023-08-26 15:16:11

Judging History

你现在查看的是最新测评结果

  • [2023-08-26 15:16:11]
  • 评测
  • 测评结果:0
  • 用时:4ms
  • 内存:3544kb
  • [2023-08-26 15:16:10]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define fi first
#define se second
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){for(auto x:v)outv(x);}
const ll inf=1001001001001001001;
ll ord(ll a){
    if(a==0)return inf;
    ll ans=0;
    while(!(a&1)){
        a>>=1;ans++;
    }
    return ans;
}
vp ans;
vvi g;
ll d(ll a,ll b){
    assert(a%2==b%2);
    ans.pb(a,b);
    return (a+b)/2;
}
vi f(vi v){
    sort(all(v));
    ll n=v.size();
    P mi(inf,0);
    rep(i,n-1)chmin(mi,P(ord(v[i+1]-v[i]),i));
    ll cnt=mi.fi,cur=mi.se+1;
    while(cnt>1&&cur<n){
        v[mi.se]=d(v[mi.se],v[cur]);cnt--;cur++;
    }
    vi nv;
    rep(i,mi.se+1)nv.pb(v[i]);
    REP(i,cur,n)nv.pb(v[i]);
    while(cnt>1&&nv.size()>1){
        ll a=d(nv.back(),nv[nv.size()-2]);
        nv.pop_back();
        nv.back()=a;
        cnt--;
    }
    if(nv.size()==1)return nv;
    ll idx=0;
    while(ord(nv[idx+1]-nv[idx])>1)idx++;
    vi al;
    {
        ll cur=0;
        while(cur+1<idx){
            nv[cur+1]=d(nv[cur],nv[cur+1]);
            if(nv[cur+1]%2!=nv[cur]%2){
                g[nv[cur+1]%2].pb(nv[cur+1]);cur++;
            }
            cur++;
        }
        if(cur<idx)al.pb(nv[cur]);
    }
    al.pb(nv[idx]);al.pb(nv[idx+1]);
    {
        ll cur=nv.size()-1;
        while(cur-1>idx+1){
            nv[cur-1]=d(nv[cur],nv[cur-1]);
            if(nv[cur-1]%2!=nv[cur]%2){
                g[nv[cur-1]%2].pb(nv[cur-1]);cur--;
            }
            cur--;
        }
        if(cur>idx+1)al.pb(nv[cur]);
    }
    return al;
}
vi consume_all(vi v){
    while(v.size()>2){
        ll a=v[v.size()-3],b=v[v.size()-2],c=v.back();
        rep(j,3)v.pop_back();
        if((a+b)/2%2==a%2){
            v.pb(c);v.pb(d(a,b));
        }
        else if((b+c)/2%2==b%2){
            v.pb(a);v.pb(d(b,c));
        }
        else{
            v.pb(b);v.pb(d(c,a));
        }
    }
    if(v.size()==2){
        v[0]=d(v[0],v[1]);v.pop_back();
    }
    return v;
}
void solve(ll n,vi v){
    ans=vp(0);g=vvi(2);
    for(ll x:v)g[x%2].pb(x);
    if(g[0].size()==0){
        consume_all(g[1]);
        return;
    }
    if(g[1].size()==0){
        consume_all(g[0]);
        return;
    }
    g[0]=f(g[0]);
    ll swapped=0;
    if(g[0].size()==1){
        g[1]=f(g[1]);
    }
    else{
        swapped=1;
        swap(g[0],g[1]);
    }
    if(g[0].size()==1&&g[1].size()==1)return;
    g[0]=consume_all(g[0]);
    if(g[0][0]%2!=swapped){
        g[1].pb(g[0][0]);
        consume_all(g[1]);
        return;
    }
    if(g[1].size()==2){
        g[0].pb(d(g[1][0],g[1][1]));
        consume_all(g[0]);
        return;
    }
    rep(i,g[1].size())rep(j,i){
        ll t=(g[1][i]+g[1][j])/2,u=g[0][0];
        if(t%4!=u%4&&t%2==u%2){
            vi ng;
            ng.pb(d(d(g[1][i],g[1][j]),u));
            rep(k,g[1].size())if(i!=k&&j!=k)ng.pb(g[1][k]);
            consume_all(ng);
            return;
        }
    }
}
int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    ll t;cin>>t;
    rep(tt,t){
        ll n;cin>>n;
        vi v(n);rep(i,n)cin>>v[i];
        solve(n,v);
        if(ans.size()==n-1){
            for(auto x:ans)cout<<x.fi<<' '<<x.se<<endl;
        }
        else{
            out(-1);
        }
    }
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 3544kb

input:

99
4
739880851158065302 19206582949872932 883064254701115295 222072661880779376
7
148399819461615003 209088712310207988 53191076581680214 445068618251612752 230505279594622109 115754892157516718 804173775829453588
2
77979357045500669 41693388829622019
3
341612949433488278 609808714829036935 19994167...

output:

739880851158065302 19206582949872932
379543717053969117 883064254701115295
631303985877542206 222072661880779376
804173775829453588 445068618251612752
148399819461615003 230505279594622109
189452549528118556 209088712310207988
115754892157516718 624621197040533170
199270630919163272 3701880445990249...

result:

wrong answer you didn't find a solution but jury did (test case 35)

Subtask #2:

score: 0
Wrong Answer

Test #16:

score: 0
Wrong Answer
time: 4ms
memory: 3440kb

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
4 2
3 1
4 4
2 2
2 2
4 2
4 2
3 1
2 0
0 0
2 0
-1
0 4
1 3
2 2
4 2
4 4
3 3
2 0
1 3
0 4
2 2
2 0
1 3
2 4
4 4
4 2
1 3
2 2
2 2
0 2
3 3
3 3
1 3
2 2
0 0
2 0
4 4
1 3
4 2
3 3
1 3
2 2
0 4
2 2
0 4
1 3
2 2
4 2
0 4
2 2
2 2
4 2
0 2
1 1
4 4
4 4
4 2
3 1
2 0
1 1
3 3
1 3
4 4
2 2
4 2
0 4
2 4
1 3
1 1
0 4
3 3...

result:

wrong answer you didn't find a solution but jury did (test case 7)

Subtask #3:

score: 0
Time Limit Exceeded

Test #34:

score: 0
Time Limit Exceeded

input:

100000
5
846784256447769304 457696478728961702 128469521648960690 597630796847754190 104256763714529164
5
658897822238868978 472135077337628566 399538027669313322 622703684108675696 425723088635325654
5
917704960887390986 140817562615382054 877934664521057998 782212806618666818 616380973421914538
8
...

output:

128469521648960690 597630796847754190
104256763714529164 363050159248357440
457696478728961702 233653461481443302
846784256447769304 345674970105202502
425723088635325654 399538027669313322
622703684108675696 412630558152319488
658897822238868978 472135077337628566
517667121130497592 565516449788248...

result:


Subtask #4:

score: 0
Time Limit Exceeded

Test #46:

score: 0
Time Limit Exceeded

input:

100
211957
911918942087402387 344230223346742784 16289402153237664 528890583619159010 886281719684850237 865484734102017297 321851390502278959 754268375474197153 237414161302130571 135637002716682378 824412491959977735 162505521049217610 246319278060116103 666703181591704279 650875500699154233 96397...

output:

999989589595986634 999967720480985884
999926091055107568 999921514477613516
999923802766360542 999893240413030728
999830205792296778 999828945334385854
999829575563341316 999827896360143458
999817412630218618 999815696246321172
999799332566033426 999755204957795808
999749165525150842 999739076047312...

result: