oj.uz

Submission #704029

# Submission time Handle Problem Language Result Execution time Memory
704029 2023-03-01T11:51:51 Z vjudge1 Bank (IZhO14_bank) C++17
19 / 100
 59 ms 736 KB 
// Problem: Elevator Rides

// #pragma GCC optimize("O3")
// #pragma GCC target("avx2")

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

#define ff first
#define ss second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define ones(x) __builtin_popcount(x)
#define remove(v)  v.erase(unique(all(v)), v.end())
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define per(i, a, b) for(int i = a; i >= b; i--)

#ifdef local
#include "C:\debug.h"
#else
#define dbg(x...) 42
#endif
#define int long long

const int N = 2e6 + 2 ;
const int MOD = 1e9 + 7 ;
const int P = 1007 ;

int n , m , a[21] , b[21] , p[200] ;
int dp[1048577] ;

void solve(){
    p[0] = 1 ;
    rep(i , 1 , 199) p[i] = p[i - 1] * P , p[i] %= MOD ;
    cin >> n >> m ;
    int hash = 0 ;
    rep(i , 1 , n) cin >> a[i] ;
    sort(a + 1 , a + 1 + n) ;
    rep(i , 1 , n) {
        int cur = (a[i] * (p[i] % MOD)) % MOD ;
        hash += cur ; hash %= MOD ;
    }
    set<int> w(a + 1 , a + 1 + n) ;
    rep(i , 1 , m) cin >> b[i] ;
    set<pair<int,int>> e ;
    rep(i , 1 , (1 << m) - 1) {
        int cur = 0 ;
        rep(mask , 0 , m - 1) {
            if((i >> mask) & 1) {
                cur += b[mask + 1] ;
            }
        }
        if(cur <= 1000 && w.count(cur)) e.insert({i , cur}) ;
    }
    vector<pair<int,int>> item(all(e)) ;
    int sz = sz(item) ;
    rep(i , 0 , (1 << sz) - 1) {
        if(ones(i) != n) continue ;
        vector<int> v ;
        int cur = 0 ;
        bool ok = 1 ;
        rep(mask , 0 , sz - 1) {
            if((i >> mask & 1)) {
                int x = ones(cur) ;
                int y = ones(item[mask].first) ;
                cur ^= item[mask].first ;
                if(x + y != ones(cur)) {
                    ok = 0 ;
                    break ;
                }
                v.pb(item[mask].second) ;
            }
        }
        sort(all(v)) ;
        int H = 0 , id = 0 ;
        for(auto& x : v) {
            id++ ;
            int add = (x * (p[id] % MOD)) % MOD ;
            H += add ; H %= MOD ;
        }
        if(H == hash) {
            cout << "YES\n" ;
            return ;
        }
    }
    cout << "NO\n" ;
}

signed main () {
	// ios::sync_with_stdio(false) ;
	// cin.tie(0) ;
	int test = 1 ;
	// cin >> test ; 
	for(int i = 1 ; i <= test ; i++) {
		solve() ;
	}
}

Compilation message

bank.cpp: In function 'void solve()':
bank.cpp:64:14: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   64 |         bool ok = 1 ;
      |              ^~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 59 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 58 ms 736 KB Output is correct
9 Correct 59 ms 284 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 59 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 58 ms 736 KB Output is correct
9 Correct 59 ms 284 KB Output is correct
10 Incorrect 2 ms 212 KB Output isn't correct
11 Halted 0 ms 0 KB -