Submission #476534

#	Time	Username	Problem	Language	Result	Execution time	Memory
476534		leaked	Football (info1cup20_football)	C++14	42 / 100	2078 ms	1048580 KiB

football

#include <bits/stdc++.h>

#define m_p make_pair
#define f first
#define s second
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<x)
#define sz(x) (int)x.size()
#define fast_ioi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long double ld;
typedef pair<long long,long long> pll;
template <class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template <class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
auto rng=bind(uniform_int_distribution<int>(1,20),mt19937(time(0)));
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifndef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
map<pair<multiset<int>,int>,int>dp;
int k;
int rec(multiset<int> vc,int h){
    assert(h>=1&&h<=k);
    if(dp.count({vc,h})){return dp[{vc,h}];}
    int ok=0;
    for(auto &j : vc){
        for(int t=h;t<=min(j,k);t++){
            multiset<int>him=vc;
            auto it=him.find(j);
            him.erase(it);
            him.insert(j-t);
//            debug()<<imie(him);
            if(!rec(him,t)) ok=1;
            if(ok) break;
        }
        if(ok) break;
    }
//    debug()<<imie(vc)imie(h)imie(ok);
    dp[{vc,h}]=ok;
    return ok;
}
signed main(){
    fast_ioi;
    int t;
//    t=1;
    cin>>t;
    srand(228);
    while(t--){
        int n;
//        n=3;k=2;
//        n=rand()%10+1;k=rand()%5+1;
        cin>>n>>k;
//        vec<int>a;
        vec<int>a(n);
//        for(auto &z : a) z=rand()%3+1;
        for(auto &z : a) cin>>z;
//        debug()<<imie(a);
        auto brute=[&](){
            dp.clear();
            multiset<int>st;
            for(auto &z : a) st.insert(z);
            return rec(st,1);
        };
        auto solve=[&](){
            ll sm=0;
            vec<int>b=a;

            for(auto &z : a) sm+=(z/k),z%=k;
            int ok=0;
            if(sm%2){
                ok=1;
            }
            map<int,int>mp;
            for(auto &z : a){
                if(z) mp[z]++;
            }
            vec<pii>vc;
            for(auto &z : mp) vc.pb(z);
            sort(all(vc));
//            int ok=0;
            for(auto &z : vc){
                if(z.s%2){
    //                cout<<1;
                    ok=1;
                    break;
                }
            }
            swap(a,b);
    //        cout<<ok;
            return ok;
        };
//        if(*max_element(all(a))<=3){
//            cout<<brute();
//            continue;
//        }
        if(k!=1 && k!=2){
            cout<<brute();
        }
        else{
            cout<<solve();
        }
//        if(brute()!=solve()){
//            debug()<<imie(a)imie(solve())imie(brute())imie(k);
//            return 0;
//        }
//        debug()<<imie(brute())imie(solve());
    }
    return 0;
}
/*
6 1
5447 7526 7703 8705 18716 19718 19895
1582 7087 7911 14379 14703 14703 19265 19265 19589 26057 32386
*/

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