Submission #729297

#	Time	Username	Problem	Language	Result	Execution time	Memory
729297		shadow_sami	Council (JOI23_council)	C++17	40 / 100	4065 ms	12692 KiB

council

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef int ll;
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
typedef pair<ll,ll> pi;
typedef map<ll,ll> mi;
typedef long double ld;
typedef vector<ld> vd;
typedef vector<vector<ld>> vvd;
typedef pair<ld,ld> pd;
#define ff first
#define ss second
#define srt(a) sort(a.begin(),a.end());
#define fip(k, n) for (ll i = k; i < n; i++)
#define fjp(k, n) for (ll j = k; j < n; j++)
#define fin(k, n) for (ll i = k; i >= n; i--)
#define fjn(k, n) for (ll j = k; j >= n; j--)
#define fp(k, n, m) for (ll k = n; k < m; k++)
#define fn(k, n, m) for (ll k = n; k >= m; k--)
#define ordered_set tree<pi, null_type,less< pi >, rb_tree_tag,tree_order_statistics_node_update>
#define totalOne(n) __builtin_popcount(n)
#define backZero(n) __builtin_ctzll(n)
#define frontZero(n) __builtin_clzll(n)
#define fx(k) for ( auto x : k )
#define test ll t;cin >> t;while (t--)
#define nli "\n"

ll n,m,tp,tp2,res,cnt,sum,tptp,ans;
const ll mx = 3e5+5;
const ll mod = 1e9+7;

bool f = false;
set<ll> st;
ll a[mx];
ll tnc[25];
ll bits[(1 << 15)];
ll na[(1 << 15)];
ll one,zero;
vi v;

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // #ifndef ONLINE_JUDGE
    //     freopen("input1.txt", "r", stdin);
    //     freopen("output1.txt", "w", stdout);
    //     freopen("error1.txt", "w", stderr);
    // #endif // ONLINE_JUDGE

        cin>>n>>m;
        ll cnst = (1 << m) - 1;
        fip(0,n){
        	cnt = 0;
        	fjp(0,m){
        		cin>>tp;
        		cnt |= (tp<<j);
        		if(tp)
        			tnc[j]++;
        	}
        	a[i] = cnt;
        	bits[cnt]++;
        	st.insert(cnt);
        }
        res = 0,one = 0,zero = 0;
        fjp(0,m){
        	if(tnc[j]==(n/2))
        		zero |= (1<<j);
        	else if(tnc[j]==(n/2)+1)
        		one |= (1<<j);
        	else if(tnc[j]>=(n/2)+2)
        		res++;
        }
        fx(st)
        	v.push_back(x);
        fip(0,(long long)v.size()){
        	bits[v[i]]--;
        	ans = 0;
        	fjp(0,(long long)v.size()){
        		if(bits[v[j]]==0)
        			continue;
        		tp = totalOne((one & (cnst ^ (v[j]&v[i]))) | (zero & (cnst ^ (v[j]|v[i]))));
        		ans = max(ans,tp+res);
        	}
        	na[v[i]] = ans;
        	bits[v[i]]++;
        }
        fip(0,n)
        	cout<<na[a[i]]<<nli;
        
    // cerr << "Time elapsed: " << setprecision(6) << 1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 8
• Subtask 3: 6 / 6
• Subtask 4: 19 / 19
• Subtask 5: 15 / 15
• Subtask 6: 0 / 22
• Subtask 7: 0 / 22