제출 #1260866

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1260866		new_acc	Council (JOI23_council)	C++20	100 / 100	596 ms	18900 KiB

council

#include <iostream>
#include <vector>
using namespace std;
constexpr int MB = 20;
constexpr int N = 3e5 + 10;
typedef pair<int,int> desc;
pair<desc, desc> dp[1 << MB];
int glosuja[MB];
int slowa[N];
int main() {
    for (int i=0;i<(1<<MB);i++) dp[i].first.second=dp[i].second.second=-1;
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        int slowo = 0, ile = 0;
        for (int b = 0; b < m; b++) {
            int t;
            scanf("%d", &t);
            glosuja[b]+=t;
            ile += t;
            slowo |= t << b;
        }
        slowa[i]=slowo;
        slowo = ~slowo & ((1<<m)-1);
        if (dp[slowo].first.first == 0) dp[slowo].first = {m-ile,i};
        else dp[slowo].second = {m-ile,i};
    }
    for (int i=(1<<m)-1;i>=0;i--) {
        for (int b=0;b<m;b++) {
            if ((i & (1 << b)) == 0) continue;
            int newi = i ^ (1<<b);
            if (dp[i].second.first) {
                dp[newi].first=dp[newi].second={dp[i].second.first-1,dp[i].second.second};
                dp[newi].first.second=dp[i].first.second;
            }
            else if (dp[i].first.first && dp[i].first.second!=dp[newi].first.second) {
                if (dp[i].first.second!=dp[newi].first.second) swap(dp[newi].first,dp[newi].second);
                dp[newi].first = {dp[i].first.first-1,dp[i].first.second};
            }
        }
    }
    for (int i = 0; i < (1 << m); i++) {
        for (int b = 0; b < m; b++) {
            if ((i & (1 << b)) != 0) continue;
            int newi = i | 1<<b;
            if (dp[newi].first<dp[i].first) {
                if (dp[i].first.second!=dp[newi].first.second) swap(dp[newi].first,dp[newi].second);
                dp[newi].first=dp[i].first;
                dp[newi].second = max(dp[newi].second,dp[i].second);
            }
            else if (dp[newi].second<dp[i].first && dp[i].first.second!=dp[newi].first.second) dp[newi].second=dp[i].first;
            else if (dp[newi].second<dp[i].second && dp[i].second.second!=dp[newi].first.second) dp[newi].second=dp[i].second;
        }
    }
    int majority = (n-2)/2 + 1;
    for (int i=0;i<n;i++) {
        int newslowo = 0, ileja=0, wyn=0, ilegeneralnie=0;
        for (int b=0;b<m;b++) {
            int red=0;
            if ((slowa[i] & (1<<b)) != 0) red=1;
            if (glosuja[b]-red == majority) {
                newslowo |= 1<<b;
                if (red==0)
                    ileja++;
                ilegeneralnie++;
            }
            else if (glosuja[b]-red > majority) wyn++;
        }
        if (dp[newslowo].first.first==ileja)
            wyn+=dp[newslowo].second.first;
        else
            wyn+=dp[newslowo].first.first;
        printf("%d\n",wyn);
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

council.cpp: In function 'int main()':
council.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
council.cpp:18:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |             scanf("%d", &t);
      |             ~~~~~^~~~~~~~~~

• 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