Submission #889619

#	Time	Username	Problem	Language	Result	Execution time	Memory
889619		vjudge1	Council (JOI23_council)	C++17	16 / 100	278 ms	16108 KiB

council

/*

author : abushbandit
contest : ---

*/

#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;

#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define ff first
#define ss second
#define pb push_back
#define rep(i,s,f) for(int i = s;i < f;i++)

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

#pragma GCC optimize("Ofast,no-stack-protector,fast-math",3)

template <class type1>
	using ordered_multiset = tree <type1, null_type, less_equal <type1>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<pair<int,int>> vii;
typedef pair<int,int> pii;

const ll INF = 1e18;
const ll MOD7 = 1e9 + 7;
const ll MOD9 = 998244353;
const ld PI = acos(-1.0);
const int N = 1e5 + 6;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
    
}

int binpow (int a, int n) {
	int res = 1;
	while (n) {
		if (n & 1)
			res *= a;
		a *= a;
		n >>= 1;
	}
	return res;
}

void start_file(string file){
	freopen((file + ".in").c_str(),"r",stdin);
	freopen((file + ".out").c_str(),"w",stdout);
}


void solve(int tc){
	
	int n,m;
	cin >> n >> m;
	int a[n][m],s[m],b[n][m];
	rep(i,0,n){
		rep(j,0,m){
			cin >> a[i][j];
			b[i][j] = a[i][j];
		}
	}
	if(n <= 3000 && m <= 3000){
		rep(j,0,m){
			int cnt = 0;
			rep(i,0,n){
				cnt += a[i][j] > 0;
			}
			s[j] = cnt;
	//		cout << s[j] << "\n";
		}
		rep(i,0,n){
			rep(j,0,m){
				a[i][j] = b[i][j];
			}
		}
		for(int i = 0;i < n;i++){
			int ans = 0;
			for(int j = 0;j < n;j++){
				if(i != j){
					int cnt = 0;
					for(int k = 0;k < m;k++){
	//					cout << s[k] << " ";
						if(s[k] - ((a[i][k] == 1) + (a[j][k] == 1)) >= (n) / 2){
							cnt++;
						}
					}
	//				cout << "\n";
					ans = max(ans,cnt);
				}
			}
			cout << ans << "\n";
		}
	} else if(m <= 2){
		rep(j,0,m){
			int cnt = 0;
			rep(i,0,n){
				cnt += a[i][j] > 0;
			}
			s[j] = cnt;
	//		cout << s[j] << "\n";
		}
		vector<int> v00,v01,v10,v11;
		for(int i = 0;i < n;i++){
			if(a[i][0] == 0 && a[i][1] == 0){
				v00.pb(i);
			} else if(a[i][0] == 0 && a[i][1] == 1){
				v01.pb(i);
			} else if(a[i][0] == 1 && a[i][1] == 1){
				v11.pb(i);
			} else{
				v10.pb(i);
			}
		}
		for(int i = 0;i < n;i++){
			int ans = 0;
			if(v00.size() > 0 && v00[0] != i){
				int h = (s[0] - (a[i][0])) >= (n / 2) + (s[1] - (a[i][1])) >= (n / 2);	
				ans = max(ans,h);
			} else if(v00.size() > 1){
				int h = (s[0] - (a[i][0])) >= (n / 2) + (s[1] - (a[i][1])) >= (n / 2);
				ans = max(ans,h);
			}
			if(v01.size() > 0 && v01[0] != i){
				int h = (s[0] - (a[i][0])) >= (n / 2) + (s[1] - (a[i][1] + 1)) >= (n / 2);
				ans = max(ans,h);
			} else if(v01.size() > 1){
				int h = (s[0] - (a[i][0])) >= (n / 2) + (s[1] - (a[i][1] + 1)) >= (n / 2);
				ans = max(ans,h);
			}
			if(v10.size() > 0 && v10[0] != i){
				int h = (s[0] - (a[i][0] + 1)) >= (n / 2) + (s[1] - (a[i][1])) >= (n / 2);
				ans = max(ans,h);
			} else if(v10.size() > 1){
				int h = (s[0] - (a[i][0] + 1)) >= (n / 2) + (s[1] - (a[i][1])) >= (n / 2);
				ans = max(ans,h);
			}
			if(v11.size() > 0 && v11[0] != i){
				int h = (s[0] - (a[i][0] + 1)) >= (n / 2) + (s[1] - (a[i][1] + 1)) >= (n / 2);
				ans = max(ans,h);
			} else if(v11.size() > 1){
				int h = (s[0] - (a[i][0] + 1)) >= (n / 2) + (s[1] - (a[i][1] + 1)) >= (n / 2);
				ans = max(ans,h);
			}
			cout << ans << "\n";
			
		}
		
	}
	
		
}

signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);                      
    
    //	start_file("");

	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);

	int test_cases = 1;
//	cin >> test_cases ;
	for(int tc = 1;tc <= test_cases;++ tc){
		solve(tc);
	}
    
}

Compilation message (stderr)

council.cpp: In function 'void solve(long long int)':
council.cpp:146:32: warning: comparisons like 'X<=Y<=Z' do not have their mathematical meaning [-Wparentheses]
  146 |     int h = (s[0] - (a[i][0])) >= (n / 2) + (s[1] - (a[i][1])) >= (n / 2);
      |             ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
council.cpp:149:32: warning: comparisons like 'X<=Y<=Z' do not have their mathematical meaning [-Wparentheses]
  149 |     int h = (s[0] - (a[i][0])) >= (n / 2) + (s[1] - (a[i][1])) >= (n / 2);
      |             ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
council.cpp:153:32: warning: comparisons like 'X<=Y<=Z' do not have their mathematical meaning [-Wparentheses]
  153 |     int h = (s[0] - (a[i][0])) >= (n / 2) + (s[1] - (a[i][1] + 1)) >= (n / 2);
      |             ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
council.cpp:156:32: warning: comparisons like 'X<=Y<=Z' do not have their mathematical meaning [-Wparentheses]
  156 |     int h = (s[0] - (a[i][0])) >= (n / 2) + (s[1] - (a[i][1] + 1)) >= (n / 2);
      |             ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
council.cpp:160:36: warning: comparisons like 'X<=Y<=Z' do not have their mathematical meaning [-Wparentheses]
  160 |     int h = (s[0] - (a[i][0] + 1)) >= (n / 2) + (s[1] - (a[i][1])) >= (n / 2);
      |             ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
council.cpp:163:36: warning: comparisons like 'X<=Y<=Z' do not have their mathematical meaning [-Wparentheses]
  163 |     int h = (s[0] - (a[i][0] + 1)) >= (n / 2) + (s[1] - (a[i][1])) >= (n / 2);
      |             ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
council.cpp:167:36: warning: comparisons like 'X<=Y<=Z' do not have their mathematical meaning [-Wparentheses]
  167 |     int h = (s[0] - (a[i][0] + 1)) >= (n / 2) + (s[1] - (a[i][1] + 1)) >= (n / 2);
      |             ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
council.cpp:170:36: warning: comparisons like 'X<=Y<=Z' do not have their mathematical meaning [-Wparentheses]
  170 |     int h = (s[0] - (a[i][0] + 1)) >= (n / 2) + (s[1] - (a[i][1] + 1)) >= (n / 2);
      |             ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
council.cpp: In function 'void start_file(std::string)':
council.cpp:75:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |  freopen((file + ".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
council.cpp:76:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |  freopen((file + ".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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