제출 #1282461

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282461		miniob	Council (JOI23_council)	C++20	100 / 100	1012 ms	51852 KiB

council

#include <bits/stdc++.h>
using namespace std;

int maska[300007];
int tab[300007][21];
int ile[27];
int dp11[1048580];
int dp12[1048580];
int dp21[1048580];
int dp22[1048580];

struct wartosc 
{
    int j1, j2;
    wartosc(int a=-1, int b=-1): j1(a), j2(b) {}
};

wartosc dop[1048580];

void dodaj(wartosc &p, int gdzie)
{
	if (gdzie == -1)
	{
		return;
	}
    else if (p.j1 == gdzie || p.j2 == gdzie)
    {
    	return;
    }
    else if (p.j1 == -1) 
    {
    	p.j1 = gdzie;
    	return;
    }
    else if (p.j2 == -1) 
    {
    	p.j2 = gdzie; 
    	return;
    }
}

void dodaj2(int maskaa, int gdzie, int k)
{
        if (gdzie == -1)
        {
        	return;
        }
        else if (dp21[maskaa] == gdzie)
        {
            if (k > dp11[maskaa])
            {
            	dp11[maskaa] = k;
            }
            return;
        }
        else if (dp22[maskaa] == gdzie)
        {
            if (k > dp12[maskaa])
            {
            	dp12[maskaa] = k;
            }
            return;
        }
        else if (dp21[maskaa] == -1 || k > dp11[maskaa]) 
        {
            if (dp21[maskaa] != -1) 
            {
                dp22[maskaa] = dp21[maskaa];
                dp12[maskaa] = dp11[maskaa];
            }
            dp21[maskaa] = gdzie;
            dp11[maskaa] = k;
        } 
        else if (dp22[maskaa] == -1 || k > dp12[maskaa]) 
        {
            dp22[maskaa] = gdzie;
            dp12[maskaa] = k;
        }
}

int main() 
{
	for(int i = 0; i < 1048577; i++)
	{
		dp11[i] = -1;
		dp12[i] = -1;
		dp21[i] = -1;
		dp22[i] = -1;
	}
	int n, m, wym;
	cin >> n >> m;
	wym = n / 2;
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			cin >> tab[i][j];
			maska[i] += (tab[i][j] << j);
			ile[j] += tab[i][j];
		}
		dodaj(dop[(1 << m) - 1 - maska[i]], i);
	}
	for (int i = 0; i < m ; i++)
	{
        for (int maskaa = 0; maskaa < (1 << m); maskaa++)
        {
            if ((maskaa & (1<<i)) == 0)
            {
                dodaj(dop[maskaa], dop[maskaa | (1<<i)].j1);
                dodaj(dop[maskaa], dop[maskaa | (1<<i)].j2);
            }
        }
    }
    for (int i = 0; i < (1 << m); i++) 
    {
        if (dop[i].j1 != -1)
        {
        	dodaj2(i, dop[i].j1, __builtin_popcount(i));
        }
        if (dop[i].j2 != -1)
        {
        	dodaj2(i, dop[i].j2, __builtin_popcount(i));
        }
    }
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < (1 << m); ++j) 
        {
            if (j & (1 << i)) 
            {
                if (dp21[j ^ (1<<i)] != -1)
                {
                	dodaj2(j, dp21[j ^ (1<<i)], dp11[j ^ (1<<i)]);
                }
                if (dp22[j ^ (1<<i)] != -1)
                {
                	dodaj2(j, dp22[j ^ (1<<i)], dp12[j ^ (1<<i)]);
                }
            }
        }
    }
	for(int i = 0; i < n; i++)
	{
		int odp = 0, maskac = 0;
		for(int j = 0; j < m; j++)
		{
			ile[j] -= tab[i][j];
			if(ile[j] == wym)
			{
				maskac += 1 << j;
			}
			else if(ile[j] > wym)
			{
				odp++;
			}
		}
		if(dp21[maskac] != i)
		{
			odp += dp11[maskac];
		}
		else
		{
			odp += dp12[maskac];	
		}
		for(int j = 0; j < m; j++)
		{
			ile[j] += tab[i][j];
		}
		cout << odp << endl;
	}
	return 0;
}

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