Submission #493971

#	Time	Username	Problem	Language	Result	Execution time	Memory
493971		balbit	Football (info1cup20_football)	C++14	100 / 100	33 ms	1348 KiB

football

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define f first
#define s second
#define pii pair<ll, ll>

#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define pb push_back

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do( T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do( T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT


signed main(){
    ios::sync_with_stdio(0), cin.tie(0);



    int t; cin>>t;
    while (t--) {
        int n,k; cin>>n>>k;

        vector<int> a(n);
        int x = 0;
        REP(i,n) {
            cin>>a[i]; x ^= a[i];
        }
        if( k == 0) {
            cout<<0<<endl;
            assert(0);
            continue;
        }
        int lbit = x&-x;
        if (k >= lbit && lbit != 0) {
            cout<<1;
        }else{
            // now think...
            // guess: only do k= 2^P ????
            for (int e : a) {
                for (int ar = 1; ar <= k && ar <= e; ar*=2) {
                    int xx = x ^ e ^ (e-ar);
                    int lb = xx & -xx;
                    if (ar < lb) {
                        assert(0);
                        cout<<1;
                        goto done;
                    }
                }
            }
            cout<<0;
        }
        done:;
    }
    cout<<endl;

}

• Subtask 1: 26 / 26
• Subtask 2: 8 / 8
• Subtask 3: 11 / 11
• Subtask 4: 8 / 8
• Subtask 5: 16 / 16
• Subtask 6: 16 / 16
• Subtask 7: 7 / 7
• Subtask 8: 8 / 8