oj.uz

Submission #810449

# Submission time Handle Problem Language Result Execution time Memory
810449 2023-08-06T09:53:22 Z azberjibiou Council (JOI23_council) C++17
0 / 100
 1166 ms 25540 KB 
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pdd pair<long double, long double>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ppi pair<pii, pii>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
const int mxN=300020;
const int mxM=25;
const int mxK=1200000;
const int MOD=1e9+7;
const ll INF=1e18;
typedef struct pnt{
    int dis, src, pos;
    pnt() : dis(), src(), pos() {}
    pnt(int dis, int src, int pos) : dis(dis), src(src), pos(pos) {}
}pnt;
int N, M;
int A[mxN];
int cnt[mxM], imp[mxN];
int one[mxN];
void input()
{
    cin >> N >> M;
    for(int i=1;i<=N;i++)
    {
        for(int j=0;j<M;j++)
        {
            int a;  cin >> a;
            A[i]+=a*(1<<j);
        }
    }
}
void make_cnt()
{
    for(int i=0;i<M;i++)
    {
        for(int j=1;j<=N;j++)   cnt[i]+=((A[j]>>i)&1);

        if(cnt[i]>=N/2+2)   for(int j=1;j<=N;j++)   one[j]++;
        if(cnt[i]<N/2)  continue;
        if(cnt[i]==N/2)
        {
            for(int j=1;j<=N;j++)   if((A[j]&(1<<i))==0)    imp[j]+=(1<<i);
        }
        if(cnt[i]==N/2+1)
        {
            for(int j=1;j<=N;j++)
            {
                if(A[j]&(1<<i)) imp[j]+=(1<<i);
                else    one[j]++;
            }
        }
    }
    for(int i=1;i<=N;i++)   imp[i]^=((1<<M)-1);
}
pair<pii, pii> D[mxK];
void bfs()
{
    queue <pnt> que;
    for(int i=1;i<=N;i++)   que.emplace(0, i, A[i]), D[A[i]].fi=pii(0, i);
    while(que.size())
    {
        auto [dis, src, now]=que.front();
        que.pop();
        for(int i=0;i<M;i++)
        {
            int nxt=(now^(1<<i));
            if(D[nxt].fi.se==0)
            {
                D[nxt].fi=pii(dis+1, src);
                que.emplace(dis+1, src, nxt);
            }
            else if(D[nxt].se.se==0 && D[nxt].fi.se!=src)
            {
                D[nxt].se=pii(dis+1, src);
                que.emplace(dis+1, src, nxt);
            }
        }
    }
}
pair<pii, pii> mrg(pair<pii, pii> a, pair<pii, pii> b)
{
    pair<pii, pii> res;
    res.fi=pii(), res.se=pii();
    vector <pii> t;
    if(a.fi.se!=0)  t.push_back(a.fi);
    if(a.se.se!=0)  t.push_back(a.se);
    if(b.fi.se!=0)  t.push_back(b.fi);
    if(b.se.se!=0)  t.push_back(b.se);
    sort(all(t));
    for(pii a : t)
    {
        if(res.fi.se==0)    res.fi=a;
        else if(res.se.se==0 && res.fi.se!=a.se)    res.se=a;
    }
    return res;
}
void imos_hanbyeol()
{
    for(int i=0;i<M;i++)
    {
        for(int j=0;j<(1<<M);j++)
        {
            if(j&(1<<i))    D[j]=mrg(D[j], D[j-(1<<i)]);
        }
    }
}
int main()
{
    gibon
    input();
    make_cnt();
    bfs();
    imos_hanbyeol();
    for(int i=1;i<=N;i++)
    {
        if(D[imp[i]].fi.se==i)  cout << one[i]+M-__builtin_popcount(imp[i])-D[imp[i]].se.fi << '\n';
        else    cout << one[i]+M-__builtin_popcount(imp[i])-D[imp[i]].fi.fi << '\n';
    }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1166 ms 25540 KB Output is correct
6 Incorrect 1095 ms 21396 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1166 ms 25540 KB Output is correct
6 Incorrect 1095 ms 21396 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

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

Subtask #4
0 / 19.0

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

Subtask #5
0 / 15.0

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

Subtask #6
0 / 22.0

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

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1166 ms 25540 KB Output is correct
6 Incorrect 1095 ms 21396 KB Output isn't correct
7 Halted 0 ms 0 KB -