結果

問題 No.2895 Zero XOR Subset
コンテスト
ユーザー 矢澤式WINTER
提出日時 2024-09-20 22:20:00
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,556 bytes
コンパイル時間 5,523 ms
コンパイル使用メモリ 316,784 KB
実行使用メモリ 17,536 KB
最終ジャッジ日時 2024-09-20 22:21:20
合計ジャッジ時間 78,651 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 14 WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
//*/
#include <atcoder/all>
using namespace atcoder;
// //*/
// #pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define ALL(x) (x).begin(),(x).end()
#define dbgv(x); for(auto now : x) cout << now << " "; cout << endl;
//using p = pair<int,int>;
using ll = long long;
using ull = unsigned long long;
//*/
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<int> vint;
random_device rnd;
mt19937 rng(rnd());

//数列のXOR基底を取る，計算量O(k^2N)
const int k = 60;
struct bitbase{
  vector<long long> d;
  vint idx;
  bitbase():d(k),idx(k){}
  long long add(long long x,int is){
    long long memo = x;
    x = tomin(x);
    //cerr << x << endl;
    //dbgv(d);
    if(x == 0) return -1;
    for(int i = k-1;i >= 0;i--){
      if(x>>i&1){
        for(int j = 0;j < k;j++)if(d[j]>>i&1){
            d[j] ^= x;
        }
        d[i] = x;
        idx[i] = is;
        return memo;
      }
    }
    return memo;
  }
  vll make(long long x){
    vll res;
    for(int i = k-1;i>=0;i--){
      if(x >> i & 1){
        res.push_back(idx[i]);
      }
    }
    return res;
  }
  long long tomin(long long x){
    for(int i = k-1;i>=0;i--){
      if(x >> i & 1) x ^= d[i];
    }
    return x;
  }
  //今の数列から0個以上のXORで作れる数のうちi番目に小さいものを取得
  //存在しない場合，-1を返す
  long long get_kth(long long _k){
    long long res = 0LL;
    for(int i = 0;i < k;i++){
      if(d[i]==0) continue;
      if(_k&1) res ^= d[i];
      _k >>= 1;
    }
    if(_k != 0) return -1;
    else return res;
  }
};

class Timer {
    public:
        Timer() {
            begin();
            elapsed_time_ = 0.0;
        }

        void begin() {
            start_time_ = chrono::system_clock::now();
        }

        double get_time() {
            chrono::system_clock::time_point end_time = chrono::system_clock::now();
            elapsed_time_ = chrono::duration_cast<std::chrono::nanoseconds>(end_time - start_time_).count();
            elapsed_time_ *= 1e-9; // nanoseconds -> seconds
            return elapsed_time_;
        }

        double get_last_time() const {
            return elapsed_time_;
        }

        bool yet(double time_limit) {
            return get_time() < time_limit;
        }

        double progress(double time_limit) {
            return get_time() / time_limit;
        }

    private:
        chrono::system_clock::time_point start_time_;
        double elapsed_time_;
};
constexpr double time_limit = 1.95;

map<ll,int> mp;
void solve(){
    Timer timer;
    int n; cin >> n;
    vll v(n); rep(i,n) cin >> v[i];
    rep(i,n){
        if(v[i] == 0){
            cout << 1 << endl;
            cout << i+1 << endl;
            return;
        }
        if(mp[v[i]]!=0){
            cout << 2 << endl;
            cout << mp[v[i]] << " " << i+1 << endl;
            return;
        }
        mp[v[i]] = i+1;
    }
    int n2 = min(40,n);
    vll vs2(n2); rep(i,n2) vs2[i] = v[i];
    for(ll i = 0;i < 1LL<<n2;i++)if(i){
        if(!(timer.yet(time_limit/2))) break;
        ll now = 0;
        rep(j,n2){
            if(i>>j&1) now ^= vs2[j];
        }
        if(now==0){
            cout << __popcount(i) << endl;
            rep(j,n2)if(i>>j&1) cout << j+1 << " ";
            cout << endl;
            return;
        }
    }
    for(ll i = (1LL<<n2)-1;i > 0;i--)if(i){
        if(!(timer.yet(time_limit))) break;
        ll now = 0;
        rep(j,n2){
            if(i>>j&1) now ^= vs2[j];
        }
        if(now==0){
            cout << __popcount(i) << endl;
            rep(j,n2)if(i>>j&1) cout << j+1 << " ";
            cout << endl;
            return;
        }
    }
    cout << -1 << endl;
}

void solve2(){
    int n; cin >> n;
    //cout << n << endl;
    ll ter = 0;
    rep(i,n-1){
        ll tar = rng();
        ter ^= tar;
        cout << tar << " ";
    }
    cout << ter << endl;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t = 1; //cin >> t;
  rep(testcase,t) solve();
}
0