oj.uz

Submission #1095956

# Submission time Handle Problem Language Result Execution time Memory
1095956 2024-10-03T13:11:54 Z 8pete8 Council (JOI23_council) C++17
16 / 100
 254 ms 345288 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
#define double long double
using namespace std;
const int mod=998244353,mxn=2e5+5,inf=1e18,minf=-1e18,lg=30;
//#undef int
int n,k,m,q;
void setIO(string name){		
	ios_base::sync_with_stdio(0); cin.tie(0);		
	freopen((name+".in").c_str(),"r",stdin);		
	freopen((name+".out").c_str(),"w",stdout);	
}
pii dp[21][(1LL<<20)];
void put(pii &a,int x){
	if(a.f>=x)a.s=a.f,a.f=x;
	else if(a.s>x)a.s=x;
}
void put2(pii &a,pii x,int add){
    if(x.f!=inf)put(a,x.f+add);
    if(x.s!=inf)put(a,x.s+add);
}
void print(int x){
    for(int i=0;i<m;i++)cout<<(!!(x&(1LL<<i)))<<" ";
    cout<<'\n';
}
int keep[mxn+10],cnt[mxn+10];
int32_t main(){
    fastio
	cin>>n>>m;
	for(int i=0;i<=m;i++)for(int j=0;j<(1LL<<m);j++)dp[i][j]={inf,inf};
	for(int i=0;i<n;i++){
		int mask=0,c=0;
		for(int j=0;j<m;j++){
			int a;cin>>a;
			if(a)mask+=(1LL<<j),c++,cnt[j]++;
		}
		keep[i]=mask;
		put(dp[0][mask],c);
	}
	for(int i=0;i<m;i++){
		for(int j=0;j<(1LL<<m);j++){
			put2(dp[i+1][j],dp[i][j],0);
			put2(dp[i+1][j^(1LL<<i)],dp[i][j],-(!!(j&(1LL<<i))));
		}
	}
	for(int i=0;i<n;i++){
		int mask=0,cant=0,ans=0,ans2=0;
		for(int j=0;j<m;j++)cnt[j]-=(!!(keep[i]&(1LL<<j)));
		for(int j=0;j<m;j++){
			if(cnt[j]==(n/2)){
				mask+=(1LL<<j);
				if((keep[i]&(1LL<<j)))cant++;
				ans2++;
			}
			else if(cnt[j]>(n)/2)ans++;
		}
		if(dp[m][mask].f==cant)ans2-=dp[m][mask].s;
		else ans2-=dp[m][mask].f;
		cout<<ans+ans2<<'\n';
		for(int j=0;j<m;j++)cnt[j]+=(!!(keep[i]&(1LL<<j)));
	}
}
/*
we can do subset dp but when we try to remove/add a bit we might add/remove it back
which will be incorrect
try keeping of "done" prefix
where at pos i we can decide what to do with the ith bit
then dont touch that bit ever again

do dp[done][x]
dp[done+1][x]=chmin(dp[done][x])
dp[done+1][x^(1<<done)]=chmin(dp[done][x]-(x&(1<<done)))
if turning off a bit -1

keep 2 answer if the first answer is the same as selecting the ith person use answer 2


*/

Compilation message

council.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
council.cpp:39:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   39 | void setIO(string name){
      |                       ^
council.cpp:45:22: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   45 | void put(pii &a,int x){
      |                      ^
council.cpp:49:31: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   49 | void put2(pii &a,pii x,int add){
      |                               ^
council.cpp:53:17: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   53 | void print(int x){
      |                 ^
council.cpp:58:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   58 | int32_t main(){
      |              ^
council.cpp: In function 'void setIO(std::string)':
council.cpp:41:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
council.cpp:42:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 170 ms 345120 KB Output is correct
6 Correct 151 ms 345068 KB Output is correct
7 Correct 159 ms 345172 KB Output is correct
8 Correct 164 ms 345052 KB Output is correct
9 Correct 215 ms 345168 KB Output is correct
10 Correct 169 ms 345012 KB Output is correct
11 Correct 174 ms 345172 KB Output is correct
12 Correct 199 ms 345200 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 604 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 468 KB Output is correct
27 Correct 0 ms 460 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 0 ms 604 KB Output is correct
30 Correct 0 ms 604 KB Output is correct
31 Correct 1 ms 600 KB Output is correct
32 Correct 0 ms 344 KB Output is correct
33 Correct 1 ms 344 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Correct 0 ms 604 KB Output is correct
39 Correct 1 ms 604 KB Output is correct
40 Correct 1 ms 600 KB Output is correct
41 Correct 3 ms 4188 KB Output is correct
42 Correct 3 ms 4188 KB Output is correct
43 Correct 2 ms 4188 KB Output is correct
44 Correct 2 ms 4188 KB Output is correct
45 Correct 3 ms 4188 KB Output is correct
46 Correct 20 ms 37464 KB Output is correct
47 Correct 19 ms 37464 KB Output is correct
48 Correct 21 ms 37468 KB Output is correct
49 Correct 19 ms 37468 KB Output is correct
50 Correct 20 ms 37464 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 170 ms 345120 KB Output is correct
6 Correct 151 ms 345068 KB Output is correct
7 Correct 159 ms 345172 KB Output is correct
8 Correct 164 ms 345052 KB Output is correct
9 Correct 215 ms 345168 KB Output is correct
10 Correct 169 ms 345012 KB Output is correct
11 Correct 174 ms 345172 KB Output is correct
12 Correct 199 ms 345200 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 604 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 468 KB Output is correct
27 Correct 0 ms 460 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 0 ms 604 KB Output is correct
30 Correct 0 ms 604 KB Output is correct
31 Correct 1 ms 600 KB Output is correct
32 Correct 0 ms 344 KB Output is correct
33 Correct 1 ms 344 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Correct 0 ms 604 KB Output is correct
39 Correct 1 ms 604 KB Output is correct
40 Correct 1 ms 600 KB Output is correct
41 Correct 3 ms 4188 KB Output is correct
42 Correct 3 ms 4188 KB Output is correct
43 Correct 2 ms 4188 KB Output is correct
44 Correct 2 ms 4188 KB Output is correct
45 Correct 3 ms 4188 KB Output is correct
46 Correct 20 ms 37464 KB Output is correct
47 Correct 19 ms 37464 KB Output is correct
48 Correct 21 ms 37468 KB Output is correct
49 Correct 19 ms 37468 KB Output is correct
50 Correct 20 ms 37464 KB Output is correct
51 Correct 164 ms 345288 KB Output is correct
52 Correct 163 ms 345168 KB Output is correct
53 Correct 244 ms 345168 KB Output is correct
54 Correct 254 ms 345172 KB Output is correct
55 Correct 1 ms 348 KB Output is correct
56 Correct 35 ms 37676 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 36 ms 4592 KB Output is correct
3 Incorrect 35 ms 4432 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 36 ms 4592 KB Output is correct
3 Incorrect 35 ms 4432 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 36 ms 4592 KB Output is correct
3 Incorrect 35 ms 4432 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 36 ms 4592 KB Output is correct
3 Incorrect 35 ms 4432 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 170 ms 345120 KB Output is correct
6 Correct 151 ms 345068 KB Output is correct
7 Correct 159 ms 345172 KB Output is correct
8 Correct 164 ms 345052 KB Output is correct
9 Correct 215 ms 345168 KB Output is correct
10 Correct 169 ms 345012 KB Output is correct
11 Correct 174 ms 345172 KB Output is correct
12 Correct 199 ms 345200 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 604 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 468 KB Output is correct
27 Correct 0 ms 460 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 0 ms 604 KB Output is correct
30 Correct 0 ms 604 KB Output is correct
31 Correct 1 ms 600 KB Output is correct
32 Correct 0 ms 344 KB Output is correct
33 Correct 1 ms 344 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Correct 0 ms 604 KB Output is correct
39 Correct 1 ms 604 KB Output is correct
40 Correct 1 ms 600 KB Output is correct
41 Correct 3 ms 4188 KB Output is correct
42 Correct 3 ms 4188 KB Output is correct
43 Correct 2 ms 4188 KB Output is correct
44 Correct 2 ms 4188 KB Output is correct
45 Correct 3 ms 4188 KB Output is correct
46 Correct 20 ms 37464 KB Output is correct
47 Correct 19 ms 37464 KB Output is correct
48 Correct 21 ms 37468 KB Output is correct
49 Correct 19 ms 37468 KB Output is correct
50 Correct 20 ms 37464 KB Output is correct
51 Correct 164 ms 345288 KB Output is correct
52 Correct 163 ms 345168 KB Output is correct
53 Correct 244 ms 345168 KB Output is correct
54 Correct 254 ms 345172 KB Output is correct
55 Correct 1 ms 348 KB Output is correct
56 Correct 35 ms 37676 KB Output is correct
57 Correct 1 ms 344 KB Output is correct
58 Correct 36 ms 4592 KB Output is correct
59 Incorrect 35 ms 4432 KB Output isn't correct
60 Halted 0 ms 0 KB -