Submission #72761431

Source Code Expand

//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
using vl=vector<long long>;
using vvl=vector<vector<long long>>;
using vvvl=vector<vector<vector<long long>>>;
using pl=pair<long long,long long>;
using vpl=vector<pair<long long,long long>>;
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ull i=(ull)(a);i<(ull)(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#include <atcoder/all>
using namespace atcoder;

long long modpow(long long a, long long n, long long mo){long long res=1;while(n>0){if(n&1){res=res*a%mo;}a=a*a%mo;n>>=1;}return res;}
long long Pow(long long a, long long n){long long res=1;while(n>0){if(n&1){res=res*a;}a=a*a;n>>=1;}return res;}

const ll MOD=998244353;
const ll INF=(1ll<<60);

int main(){
  ll T;
  cin>>T;
  rep(jfdoat,T){
    ull q,L,R;
    cin>>q>>L>>R;
    
      ll cnt=0;
      if(L%2==0 && R%2==1){
        cnt=(R-L+1)/2;
      }
      if(L%2==0 && R%2==0){
        cnt=(R-L+2)/2;
      }
      if(L%2==1 && R%2==1){
        cnt=(R-L+2)/2;
      }
      if(L%2==1 && R%2==0){
        if((popcount(L)&1)==(popcount(R)&1)){
          cnt=(R-L+3)/2;
        }
        else{
        bitset<63> l(L);
        bitset<63> r(R);
        bool canl=true;
        rep(i,63){
          if((!l.test(i)) && L+((ull)1<<i)<=R) canl=false;
        }
        bool canr=true;
        rep(i,63){
          if(r.test(i) && L<=R-((ull)1<<i)) canr=false;
        }
        if(canl || canr){
          cnt=(R-L+3)/2;
        }
        else{
          cnt=(R-L+1)/2;
        }
        }
      }
      if(q==0) cout<<cnt<<endl;
    
    if(q==1){
      string S="";
      if(L%2==0 && R%2==1){
        //cnt=(R-L+1)/2;
        bool par=0;
        rep(i,L,R+1){
          if((popcount(i)&1)==par) S+="1";
          else S+="0";
        }
      }
      if(L%2==0 && R%2==0){
        //cnt=(R-L+2)/2;
        bool par=(popcount(R)&1);
        rep(i,L,R+1){
          if((popcount(i)&1)==par) S+="1";
          else S+="0";
        }
      }
      if(L%2==1 && R%2==1){
        //cnt=(R-L+2)/2;
        bool par=(popcount(L)&1);
        rep(i,L,R+1){
          if((popcount(i)&1)==par) S+="1";
          else S+="0";
        }
      }
      if(L%2==1 && R%2==0){
        if((popcount(L)&1)==(popcount(R)&1)){
          //cnt=(R-L+3)/2;
          bool par=(popcount(L)&1);
        rep(i,L,R+1){
          if((popcount(i)&1)==par) S+="1";
          else S+="0";
        }
        }
        else{
        bitset<63> l(L);
        bitset<63> r(R);
        bool canl=true;
        rep(i,63){
          if(!l.test(i) && (L+((ull)1<<i)<=R)) canl=false;
        }
        bool canr=true;
        rep(i,63){
          if(r.test(i) && (L<=R-((ull)1<<i))) canr=false;
        }
        if(canl){
          //cnt=(R-L+3)/2;
          bool par=(popcount(R)&1);
          S+="1";
        rep(i,L+1,R+1){
          if((popcount(i)&1)==par) S+="1";
          else S+="0";
        }
        }
        else if(canr){
          //cnt=(R-L+3)/2;
          bool par=(popcount(L)&1);
        rep(i,L,R){
          if((popcount(i)&1)==par) S+="1";
          else S+="0";
        }
        S+="1";
        }
        else{
          //cnt=(R-L+1)/2;
          bool par=(popcount(L)&1);
        rep(i,L,R+1){
          if((popcount(i)&1)==par) S+="1";
          else S+="0";
        }
        }
        }
      }
      ll coun=0;
      rep(i,S.size()){
        if(S[i]=='1') coun++;
      }
      if(coun!=cnt) while(true){}
      cout<<S<<endl;
    }
  }
}

Submission Info

Submission Time
Task B - Hamming Distance is not 1
User number_cat
Language C++23 (GCC 15.2.0)
Score 0
Code Size 3875 Byte
Status WA
Exec Time 312 ms
Memory 12212 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 800
Status
AC × 1
AC × 25
WA × 28
Set Name Test Cases
Sample sample.txt
All 1_1.txt, 1_10.txt, 1_2.txt, 1_3.txt, 1_4.txt, 1_5.txt, 1_6.txt, 1_7.txt, 1_8.txt, 1_9.txt, 2_1.txt, 2_10.txt, 2_11.txt, 2_12.txt, 2_13.txt, 2_14.txt, 2_2.txt, 2_3.txt, 2_4.txt, 2_5.txt, 2_6.txt, 2_7.txt, 2_8.txt, 2_9.txt, 3_1.txt, 3_10.txt, 3_11.txt, 3_12.txt, 3_13.txt, 3_14.txt, 3_15.txt, 3_16.txt, 3_17.txt, 3_18.txt, 3_19.txt, 3_2.txt, 3_20.txt, 3_21.txt, 3_22.txt, 3_23.txt, 3_24.txt, 3_25.txt, 3_26.txt, 3_27.txt, 3_28.txt, 3_3.txt, 3_4.txt, 3_5.txt, 3_6.txt, 3_7.txt, 3_8.txt, 3_9.txt, sample.txt
Case Name Status Exec Time Memory
1_1.txt WA 302 ms 11952 KiB
1_10.txt WA 294 ms 11252 KiB
1_2.txt WA 294 ms 11192 KiB
1_3.txt WA 300 ms 11016 KiB
1_4.txt WA 299 ms 10992 KiB
1_5.txt WA 301 ms 11016 KiB
1_6.txt WA 295 ms 12212 KiB
1_7.txt WA 297 ms 10768 KiB
1_8.txt WA 300 ms 10636 KiB
1_9.txt WA 301 ms 11172 KiB
2_1.txt WA 3 ms 3644 KiB
2_10.txt AC 22 ms 11300 KiB
2_11.txt AC 23 ms 11100 KiB
2_12.txt AC 24 ms 11296 KiB
2_13.txt AC 23 ms 11176 KiB
2_14.txt WA 10 ms 3764 KiB
2_2.txt AC 15 ms 11192 KiB
2_3.txt AC 17 ms 11252 KiB
2_4.txt AC 23 ms 11104 KiB
2_5.txt AC 15 ms 11164 KiB
2_6.txt AC 15 ms 11244 KiB
2_7.txt AC 15 ms 11192 KiB
2_8.txt AC 23 ms 11192 KiB
2_9.txt AC 23 ms 11192 KiB
3_1.txt WA 312 ms 3424 KiB
3_10.txt WA 19 ms 11204 KiB
3_11.txt WA 19 ms 11096 KiB
3_12.txt AC 12 ms 10560 KiB
3_13.txt AC 16 ms 10520 KiB
3_14.txt WA 20 ms 10624 KiB
3_15.txt WA 16 ms 10500 KiB
3_16.txt AC 12 ms 10700 KiB
3_17.txt WA 14 ms 7592 KiB
3_18.txt WA 16 ms 7636 KiB
3_19.txt WA 18 ms 7588 KiB
3_2.txt WA 158 ms 11300 KiB
3_20.txt AC 15 ms 7552 KiB
3_21.txt WA 16 ms 7584 KiB
3_22.txt WA 16 ms 7764 KiB
3_23.txt AC 12 ms 6804 KiB
3_24.txt WA 21 ms 6772 KiB
3_25.txt WA 19 ms 6768 KiB
3_26.txt WA 17 ms 6116 KiB
3_27.txt WA 15 ms 5952 KiB
3_28.txt WA 10 ms 3732 KiB
3_3.txt AC 20 ms 11088 KiB
3_4.txt AC 20 ms 11196 KiB
3_5.txt AC 14 ms 11060 KiB
3_6.txt AC 13 ms 11096 KiB
3_7.txt AC 13 ms 11172 KiB
3_8.txt AC 13 ms 11108 KiB
3_9.txt AC 13 ms 11116 KiB
sample.txt AC 2 ms 3592 KiB