QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#783645#1968. Science FictionGourab_BiswasWA 6ms5688kbC++206.7kb2024-11-26 11:09:542024-11-26 11:09:58

Judging History

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

  • [2024-11-26 11:09:58]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:5688kb
  • [2024-11-26 11:09:54]
  • 提交

answer


///jai sri krishna
///jai maa kali


#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace __gnu_pbds;


typedef long long ll;
typedef long double ld;
typedef tree<
ll,
null_type,
less_equal<ll>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define db double
#define pii pair< pair<ll,ll>, ll >
#define f(i,a,b) for(ll i=a;i<b;i++)
#define fi(i,a,b,c) for(ll i=a;i<b;i+=c)
#define fr(i,a,b) for(ll i=a;i>=b;i--)
#define fri(i,a,b,c) for(ll i=a;i>=b;i-=c)
#define pb push_back
#define ss second
#define ff first
#define in insert
#define sq(x)  (x*x)
#define all(a)  a.begin(),a.end()
#define nl "\n"
#define mnpq  priority_queue <pii, vector<pii>, greater<pii> >

ll gcd(ll a,ll b){
       if(b==0)return a;
       return gcd(b,a%b);
}
int getRandom(int L,int R)
{
    return rng()%(R-L+1) + L;
}

ll lcm(ll a,ll b){
       return ((a)/gcd(a,b))*b;
}

ll bigmod(ll a,ll n,ll md){
       if(n==0){
           return 1;
       }
       if(n==1){
           return a%md;
       }
       ll d= bigmod(a,n/2,md);
       if(n%2==0){
           return (d*d)%md;
       }
       else{
           return ( ((d*d)%md) * (a%md) )%md;
       }
}

bool sortbysec(const pair<int,int> &a,
            const pair<int,int> &b)
{

    if(a.first==b.first){
         return (a.second > b.second);
    }

    return (a.first< b.first);
}


const ll  N = 103000;
const ll mod = 998244353;

const ll neginf= -1e18;
const ll inf = 1e9;
const ld eps= 1e-9;

/// Solve part by part
/// Think small case
/// Think reverse order


/// test against atleast 10 cases

/// give 10 min before submission
/// wrong submission 20 min penalty


/// use binary search for maximum minimum problem
/// use broute force to check test case in another solution




ll cal(ll n){

   ll f=1;

   f(i,1,n+1)f=f*2;

   return f;
}

bool pos(ll i,ll j){

   if(i<j)swap(i,j);

   ll df=0;
    while(i>0){
        ll d=i%2;
        ll e=j%2;
        i/=2;
        j/=2;
        if(d!=e)df++;
        if(df>1)break;
    }

    return df==1;

}

vector<ll>v[N];
ll vis[N];
ll dis[N];
ll par[N];

set<ll>upd;

void bfs(ll d,ll chi){

    vis[d]=1;

    queue<ll>q;
    par[d]=-1;

    dis[d]=0;


    upd.in(d);


    ll pr=d;

    ll hoi=0;

    q.push(d);

    while(!q.empty()){

         if(hoi==1)break;

         ll d=q.front();
         q.pop();
         for(ll ch:v[d]){
              if(vis[ch]==0){
                  vis[ch]=1;

                 //cout<<"make vis "<<ch<<endl;
                  q.push(ch);
                  par[ch]=d;
                  //cout<<ch<<endl;

                  upd.in(ch);

                  if(ch==chi){

                     hoi=1;
                     break;
                  }
              }
         }
    }

}

int main(){

       ios_base::sync_with_stdio(false);
       cin.tie(NULL);
       cout.tie(NULL);

       ll n;
       cin>>n;
       ll m=cal(n);
       ll a[m];
       ll b[m];

       map<ll,ll>mp;

       f(i,0,m){
         cin>>a[i];
         mp[a[i]]=i;
         b[i]=a[i];
       }
       sort(b,b+m);

       f(i,0,m){
         f(j,i+1,m){
             if(pos(i,j)){
                  v[i].pb(j);
                  v[j].pb(i);
             }
         }
       }



        vector<pair<ll,ll>>ans;


        ll bd=0;
        while(1){


        ll cd=0;
       f(i,0,m){

          if(a[i]==b[i])continue;

          ///swap

          ll chi=mp[b[i]]; ///chi= amar samner kake chai tar pos

         // cout<<"Chi "<<chi<<endl;

          bfs(i,chi);  ///i= amar position

         // cout<<i<<" "<<chi<<endl;

          ll nd=chi;

        //  cout<<vis[nd]<<endl;

          vector<ll>vv;

          ll mn=i;
          while(nd!=-1){

               /// cout<<nd<<endl;
                vv.pb(nd);
                mn=min(mn,nd);
                nd=par[nd];

          }

          if(vv.size()>2){
                 for(ll x:upd){
                      vis[x]=0;
                      dis[x]=0;
                      par[x]=0;
                  }
                   upd.clear();

            continue;
          }

          cd=1;


          f(i,0,vv.size()-1){
             swap(a[vv[i]],a[vv[i+1]]);

             mp[a[vv[i]]]=vv[i];
             mp[a[vv[i+1]]]=vv[i+1];

             ans.pb({vv[i],vv[i+1]});
          }
          ///chi theke amar position e asci

          if(mn<i){///ami lower pos er value use korci
             ll sp=0;
             f(j,1,vv.size()){
                if(vv[j]==mn){
                     sp=vv[j-1];
                     break;
                }
             }

             swap(a[mn],a[sp]);

             ans.pb({mn,sp});
             mp[a[mn]]=mn;
             mp[a[sp]]=sp;



          }

          for(ll x:upd){
             vis[x]=0;
             dis[x]=0;
             par[x]=0;
          }
          upd.clear();

       }

       if(cd==0)break;

        }


       f(i,0,m){

          if(a[i]==b[i])continue;

          ///swap

          ll chi=mp[b[i]]; ///chi= amar samner kake chai tar pos

         // cout<<"Chi "<<chi<<endl;

          bfs(i,chi);  ///i= amar position

         // cout<<i<<" "<<chi<<endl;

          ll nd=chi;

        //  cout<<vis[nd]<<endl;

          vector<ll>vv;

          ll mn=i;
          while(nd!=-1){

               /// cout<<nd<<endl;
                vv.pb(nd);
                mn=min(mn,nd);
                nd=par[nd];

          }


          f(i,0,vv.size()-1){
             swap(a[vv[i]],a[vv[i+1]]);

             mp[a[vv[i]]]=vv[i];
             mp[a[vv[i+1]]]=vv[i+1];

             ans.pb({vv[i],vv[i+1]});
          }
          ///chi theke amar position e asci

          if(mn<i){///ami lower pos er value use korci
             ll sp=0;
             f(j,1,vv.size()){
                if(vv[j]==mn){
                     sp=vv[j-1];
                     break;
                }
             }

             swap(a[mn],a[sp]);

             ans.pb({mn,sp});
             mp[a[mn]]=mn;
             mp[a[sp]]=sp;



          }

          for(ll x:upd){
             vis[x]=0;
             dis[x]=0;
             par[x]=0;
          }
          upd.clear();

       }






       cout<<ans.size()<<nl;

       f(i,0,ans.size()){
        ll ft=min(ans[i].ff,ans[i].ss);
        ll st=max(ans[i].ff,ans[i].ss);
          cout<<ft<<" "<<st<<nl;
       }






}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 5592kb

input:

2
3 2 10 4

output:

2
0 1
2 3

result:

ok nice! 2 moves

Test #2:

score: 0
Accepted
time: 0ms
memory: 3680kb

input:

1
10 100

output:

0

result:

ok nice! 0 moves

Test #3:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

1
824838 992401

output:

0

result:

ok nice! 0 moves

Test #4:

score: 0
Accepted
time: 0ms
memory: 5688kb

input:

2
208395 17211 250690 874014

output:

1
0 1

result:

ok nice! 1 moves

Test #5:

score: -100
Wrong Answer
time: 6ms
memory: 3944kb

input:

8
991318 655714 983340 496226 752852 888298 572661 729100 426124 437775 8096 28612 303846 295897 970760 179029 702449 407420 945406 352294 960516 484993 724888 495235 156841 451864 95506 869159 61631 296168 279240 260130 901551 726353 298872 221580 982372 394731 720187 656498 595457 381795 759187 36...

output:

1234
33 35
29 61
0 29
73 75
0 73
138 139
145 147
211 243
161 225
0 161
112 240
0 112
231 247
0 231
30 62
14 30
6 14
2 6
0 2
2 10
0 2
0 1
0 2
13 77
5 13
1 5
0 1
0 2
0 1
12 44
4 12
0 4
0 1
1 3
0 4
5 69
4 5
3 11
1 3
1 5
1 3
82 210
18 82
2 18
2 6
2 18
22 54
6 22
6 7
6 22
9 137
8 9
11 139
9 11
43 171
11 ...

result:

wrong answer invalid swap pair