oj.uz

Submission #955466

# Submission time Handle Problem Language Result Execution time Memory
955466 2024-03-30T13:50:59 Z LCJLY Council (JOI23_council) C++14
62 / 100
 498 ms 123536 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<pii,pii>pi2;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n,m;
int arr[300005];
int cnt[25];

vector<int>sub[300005];

pi2 f(pi2 a, int b, int c){
	if(b>=a.first.first){
		if(a.first.second==c){
			a.first={b,c};
		}
		else{
			a.second=a.first;
			a.first={b,c};
		}
	}
	else if(b>=a.second.first){
		if(a.first.second!=c) a.second={b,c};
	}
	return a;
}

pi2 memo[25][300005];
bool vis[25][300005];

void out(int x){
	for(int y=0;y<m;y++){
		cout << ((x&(1<<y))>0);
	}
	cout << endl;
}

pi2 dp(int index, int mask){	
	if(index>=m){
		pi2 cur={{0,0},{0,0}};
		int num=__builtin_popcount(mask);
		if(sub[mask].size()==1){
			cur.first={num,sub[mask][0]};
		}
		else if(sub[mask].size()>1){
			cur.first={num,sub[mask][0]};
			cur.second={num,sub[mask][1]};
		}
		//if(cur.first.first>=4){
			//show2(a,cur.first.first,b,cur.first.second);
			//show2(c,cur.second.first,d,cur.second.second);
			//cout <<  "mask ";
			//out(mask);
		//}
		return cur;
		
	}
	if(vis[index][mask]) return memo[index][mask];
	pi2 ans=dp(index+1,mask);
	if(mask&(1<<index)){
		pi2 hold=dp(index+1,mask^(1<<index));
		ans=f(ans,hold.first.first,hold.first.second);
		ans=f(ans,hold.second.first,hold.second.second);
	}	
	vis[index][mask]=true;
	return memo[index][mask]=ans;
}

void dfs(int index, int mask){
	if(mask==0) return;
	if(sub[mask].size()>=2) return;
	if(sub[mask].size()>0&&sub[mask][0]==index) return;
	if(sub[mask].size()>1&&sub[mask][1]==index) return;
	sub[mask].push_back(index);
	for(int x=0;x<m;x++){
		if(mask&(1<<x)){
			dfs(index,mask^(1<<x));
		}
	}
}

void solve(){
	cin >> n >> m;
	
	int temp;
	for(int x=0;x<n;x++){
		int inv=0;
		for(int y=0;y<m;y++){
			cin >> temp;
			arr[x]+=temp*(1<<y);
			cnt[y]+=temp;
			inv+=(1-temp)*(1<<y);
		}
		dfs(x,inv);
	}
	
	for(int x=0;x<n;x++){
		for(int y=0;y<m;y++){
			if(arr[x]&(1<<y)) cnt[y]--;
		}
		
		int crit=n/2;
		int safe=0;
		int hold=0;
		for(int y=0;y<m;y++){
			if(cnt[y]>crit) safe++; 
			if(cnt[y]==crit) hold+=(1<<y);
		}
		
		//show2(x,x,safe,safe);
		//out(hold);
		
		pi2 take=dp(0,hold);
		//show2(aa,take.first.first,bb,take.first.second);
		//show2(cc,take.second.first,dd,take.second.second);
		if(take.first.second==x){
			safe+=take.second.first;
		}
		else safe+=take.first.first;
		
		for(int y=0;y<m;y++){
			if(arr[x]&(1<<y)) cnt[y]++;
		}
		
		cout << safe << "\n";
	}		
	
	
}
 
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16728 KB Output is correct
2 Correct 5 ms 35420 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Runtime error 38 ms 30812 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16728 KB Output is correct
2 Correct 5 ms 35420 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Runtime error 38 ms 30812 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 44 ms 16336 KB Output is correct
3 Correct 42 ms 16380 KB Output is correct
4 Correct 33 ms 14428 KB Output is correct
5 Correct 48 ms 16468 KB Output is correct
6 Correct 32 ms 14160 KB Output is correct
7 Correct 48 ms 16464 KB Output is correct
8 Correct 2 ms 12632 KB Output is correct
9 Correct 3 ms 12688 KB Output is correct
10 Correct 3 ms 14684 KB Output is correct
11 Correct 3 ms 14684 KB Output is correct
12 Correct 2 ms 14684 KB Output is correct
13 Correct 2 ms 12728 KB Output is correct
14 Correct 3 ms 14684 KB Output is correct
15 Correct 3 ms 14684 KB Output is correct
16 Correct 3 ms 14684 KB Output is correct
17 Correct 3 ms 14684 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 44 ms 16336 KB Output is correct
3 Correct 42 ms 16380 KB Output is correct
4 Correct 33 ms 14428 KB Output is correct
5 Correct 48 ms 16468 KB Output is correct
6 Correct 32 ms 14160 KB Output is correct
7 Correct 48 ms 16464 KB Output is correct
8 Correct 2 ms 12632 KB Output is correct
9 Correct 3 ms 12688 KB Output is correct
10 Correct 3 ms 14684 KB Output is correct
11 Correct 3 ms 14684 KB Output is correct
12 Correct 2 ms 14684 KB Output is correct
13 Correct 2 ms 12728 KB Output is correct
14 Correct 3 ms 14684 KB Output is correct
15 Correct 3 ms 14684 KB Output is correct
16 Correct 3 ms 14684 KB Output is correct
17 Correct 3 ms 14684 KB Output is correct
18 Correct 3 ms 16732 KB Output is correct
19 Correct 3 ms 18780 KB Output is correct
20 Correct 163 ms 32760 KB Output is correct
21 Correct 148 ms 30800 KB Output is correct
22 Correct 166 ms 30800 KB Output is correct
23 Correct 139 ms 32980 KB Output is correct
24 Correct 130 ms 32868 KB Output is correct
25 Correct 177 ms 32872 KB Output is correct
26 Correct 182 ms 32968 KB Output is correct
27 Correct 5 ms 31068 KB Output is correct
28 Correct 3 ms 16984 KB Output is correct
29 Correct 3 ms 18780 KB Output is correct
30 Correct 3 ms 20828 KB Output is correct
31 Correct 4 ms 23044 KB Output is correct
32 Correct 4 ms 25120 KB Output is correct
33 Correct 4 ms 26968 KB Output is correct
34 Correct 4 ms 29020 KB Output is correct
35 Correct 5 ms 31068 KB Output is correct
36 Correct 5 ms 31324 KB Output is correct
37 Correct 3 ms 16732 KB Output is correct
38 Correct 3 ms 19032 KB Output is correct
39 Correct 3 ms 20828 KB Output is correct
40 Correct 4 ms 23028 KB Output is correct
41 Correct 4 ms 25004 KB Output is correct
42 Correct 4 ms 26972 KB Output is correct
43 Correct 5 ms 29236 KB Output is correct
44 Correct 5 ms 31068 KB Output is correct
45 Correct 6 ms 31324 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 44 ms 16336 KB Output is correct
3 Correct 42 ms 16380 KB Output is correct
4 Correct 33 ms 14428 KB Output is correct
5 Correct 48 ms 16468 KB Output is correct
6 Correct 32 ms 14160 KB Output is correct
7 Correct 48 ms 16464 KB Output is correct
8 Correct 2 ms 12632 KB Output is correct
9 Correct 3 ms 12688 KB Output is correct
10 Correct 3 ms 14684 KB Output is correct
11 Correct 3 ms 14684 KB Output is correct
12 Correct 2 ms 14684 KB Output is correct
13 Correct 2 ms 12728 KB Output is correct
14 Correct 3 ms 14684 KB Output is correct
15 Correct 3 ms 14684 KB Output is correct
16 Correct 3 ms 14684 KB Output is correct
17 Correct 3 ms 14684 KB Output is correct
18 Correct 3 ms 16732 KB Output is correct
19 Correct 3 ms 18780 KB Output is correct
20 Correct 163 ms 32760 KB Output is correct
21 Correct 148 ms 30800 KB Output is correct
22 Correct 166 ms 30800 KB Output is correct
23 Correct 139 ms 32980 KB Output is correct
24 Correct 130 ms 32868 KB Output is correct
25 Correct 177 ms 32872 KB Output is correct
26 Correct 182 ms 32968 KB Output is correct
27 Correct 5 ms 31068 KB Output is correct
28 Correct 3 ms 16984 KB Output is correct
29 Correct 3 ms 18780 KB Output is correct
30 Correct 3 ms 20828 KB Output is correct
31 Correct 4 ms 23044 KB Output is correct
32 Correct 4 ms 25120 KB Output is correct
33 Correct 4 ms 26968 KB Output is correct
34 Correct 4 ms 29020 KB Output is correct
35 Correct 5 ms 31068 KB Output is correct
36 Correct 5 ms 31324 KB Output is correct
37 Correct 3 ms 16732 KB Output is correct
38 Correct 3 ms 19032 KB Output is correct
39 Correct 3 ms 20828 KB Output is correct
40 Correct 4 ms 23028 KB Output is correct
41 Correct 4 ms 25004 KB Output is correct
42 Correct 4 ms 26972 KB Output is correct
43 Correct 5 ms 29236 KB Output is correct
44 Correct 5 ms 31068 KB Output is correct
45 Correct 6 ms 31324 KB Output is correct
46 Correct 5 ms 35416 KB Output is correct
47 Correct 254 ms 49932 KB Output is correct
48 Correct 229 ms 41296 KB Output is correct
49 Correct 243 ms 41576 KB Output is correct
50 Correct 188 ms 41436 KB Output is correct
51 Correct 177 ms 41808 KB Output is correct
52 Correct 239 ms 41556 KB Output is correct
53 Correct 286 ms 50216 KB Output is correct
54 Correct 10 ms 47964 KB Output is correct
55 Correct 6 ms 43612 KB Output is correct
56 Correct 7 ms 43612 KB Output is correct
57 Correct 6 ms 45660 KB Output is correct
58 Correct 7 ms 47964 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 44 ms 16336 KB Output is correct
3 Correct 42 ms 16380 KB Output is correct
4 Correct 33 ms 14428 KB Output is correct
5 Correct 48 ms 16468 KB Output is correct
6 Correct 32 ms 14160 KB Output is correct
7 Correct 48 ms 16464 KB Output is correct
8 Correct 2 ms 12632 KB Output is correct
9 Correct 3 ms 12688 KB Output is correct
10 Correct 3 ms 14684 KB Output is correct
11 Correct 3 ms 14684 KB Output is correct
12 Correct 2 ms 14684 KB Output is correct
13 Correct 2 ms 12728 KB Output is correct
14 Correct 3 ms 14684 KB Output is correct
15 Correct 3 ms 14684 KB Output is correct
16 Correct 3 ms 14684 KB Output is correct
17 Correct 3 ms 14684 KB Output is correct
18 Correct 3 ms 16732 KB Output is correct
19 Correct 3 ms 18780 KB Output is correct
20 Correct 163 ms 32760 KB Output is correct
21 Correct 148 ms 30800 KB Output is correct
22 Correct 166 ms 30800 KB Output is correct
23 Correct 139 ms 32980 KB Output is correct
24 Correct 130 ms 32868 KB Output is correct
25 Correct 177 ms 32872 KB Output is correct
26 Correct 182 ms 32968 KB Output is correct
27 Correct 5 ms 31068 KB Output is correct
28 Correct 3 ms 16984 KB Output is correct
29 Correct 3 ms 18780 KB Output is correct
30 Correct 3 ms 20828 KB Output is correct
31 Correct 4 ms 23044 KB Output is correct
32 Correct 4 ms 25120 KB Output is correct
33 Correct 4 ms 26968 KB Output is correct
34 Correct 4 ms 29020 KB Output is correct
35 Correct 5 ms 31068 KB Output is correct
36 Correct 5 ms 31324 KB Output is correct
37 Correct 3 ms 16732 KB Output is correct
38 Correct 3 ms 19032 KB Output is correct
39 Correct 3 ms 20828 KB Output is correct
40 Correct 4 ms 23028 KB Output is correct
41 Correct 4 ms 25004 KB Output is correct
42 Correct 4 ms 26972 KB Output is correct
43 Correct 5 ms 29236 KB Output is correct
44 Correct 5 ms 31068 KB Output is correct
45 Correct 6 ms 31324 KB Output is correct
46 Correct 5 ms 35416 KB Output is correct
47 Correct 254 ms 49932 KB Output is correct
48 Correct 229 ms 41296 KB Output is correct
49 Correct 243 ms 41576 KB Output is correct
50 Correct 188 ms 41436 KB Output is correct
51 Correct 177 ms 41808 KB Output is correct
52 Correct 239 ms 41556 KB Output is correct
53 Correct 286 ms 50216 KB Output is correct
54 Correct 10 ms 47964 KB Output is correct
55 Correct 6 ms 43612 KB Output is correct
56 Correct 7 ms 43612 KB Output is correct
57 Correct 6 ms 45660 KB Output is correct
58 Correct 7 ms 47964 KB Output is correct
59 Correct 279 ms 46632 KB Output is correct
60 Correct 326 ms 119636 KB Output is correct
61 Correct 298 ms 119796 KB Output is correct
62 Correct 301 ms 121940 KB Output is correct
63 Correct 326 ms 81044 KB Output is correct
64 Correct 422 ms 122264 KB Output is correct
65 Correct 498 ms 122452 KB Output is correct
66 Correct 272 ms 47600 KB Output is correct
67 Correct 230 ms 51284 KB Output is correct
68 Correct 329 ms 51248 KB Output is correct
69 Correct 479 ms 123536 KB Output is correct
70 Correct 50 ms 103508 KB Output is correct
71 Correct 10 ms 76888 KB Output is correct
72 Correct 11 ms 66648 KB Output is correct
73 Correct 16 ms 103532 KB Output is correct
74 Correct 20 ms 115296 KB Output is correct
75 Correct 101 ms 121260 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16728 KB Output is correct
2 Correct 5 ms 35420 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Runtime error 38 ms 30812 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -