Submission #160741

#	Time	Username	Problem	Language	Result	Execution time	Memory
160741		stoyan_malinin	Red-blue table (IZhO19_stones)	C++14	0 / 100	94 ms	2544 KiB

stones

#include<iostream>
#include<cstring>
#include<random>
#include<vector>
#include<algorithm>

using namespace std;

int n, m;
int a[10][10];

int cnt = 0;
int answer = 0;

int evaluate()
{
    int A = 0, B = 0;

    for(int i = 0;i<n;i++)
    {
        int cnt[2] = {0, 0};
        for(int j = 0;j<m;j++)
        {
            cnt[ a[i][j] ]++;
        }

        if(cnt[0]>cnt[1]) A++;
    }

    for(int j = 0;j<m;j++)
    {
        int cnt[2] = {0, 0};
        for(int i = 0;i<n;i++)
        {
            cnt[ a[i][j] ]++;
        }

        if(cnt[0]<cnt[1]) B++;
    }

    return A + B;
}

void gen(int i, int j)
{
    if(i==n)
    {
        answer = max(answer, evaluate());
        return;
    }
    if(j==m)
    {
        gen(i+1, 0);
        return;
    }

    a[i][j] = 0;
    gen(i, j+1);

    a[i][j] = 1;
    gen(i, j+1);
}

vector <int> ruined;
vector <int> toAdd[1005];
vector <int> cnt2Columns[1005];

int bestN, bestM, bestRows;

bool matrix[1005][1005];

int myCalc(int n, int m)
{
    ruined.clear();
    for(int i = 0;i<=max(n, m);i++)
    {
        toAdd[i].clear();
        cnt2Columns[i].clear();
    }
    for(int j = 0;j<m;j++)
    {
        cnt2Columns[0].push_back(j);
    }

    if(answer<m)
    {
        answer = m;

        bestN = n;
        bestM = m;
        bestRows = -1;
    }

    for(int row = 0;row<n;row++)
    {
        /*
        for(int cnt = 0;cnt<=row;cnt++)
        {
            cout << cnt << ":";
            for(int x: cnt2Columns[cnt]) cout << " " << x;
            cout << '\n';
        }
        cout << " ---- --- --- " << '\n';
        */

        int toFill = m/2 + 1;
        for(int i = 0;i<ruined.size();i++)
        {
            toFill--;
            if(toFill==0) break;
        }

        for(int cnt = 0;cnt<=row;cnt++)
        {
            while(toFill>0 && cnt2Columns[cnt].empty()==false)
            {
                toAdd[cnt+1].push_back(cnt2Columns[cnt].back());

                toFill--;
                cnt2Columns[cnt].pop_back();
            }
        }
        for(int cnt = 0;cnt<=(n-1)/2;cnt++)
        {
            while(toAdd[cnt].empty()==false)
            {
                cnt2Columns[cnt].push_back(toAdd[cnt].back());
                toAdd[cnt].pop_back();
            }
        }
        while(toAdd[(n+1)/2].empty()==false)
        {
            ruined.push_back(toAdd[(n+1)/2].back());
            toAdd[(n+1)/2].pop_back();
        }

        int curr = row + 1;
        for(int cnt = 0;cnt<=(n-1)/2;cnt++)
        {
            curr += cnt2Columns[cnt].size();
        }

        if(answer<curr)
        {
            answer = curr;

            bestN = n;
            bestM = m;
            bestRows = row;
        }
    }

    return answer;
}

int recover()
{
    ruined.clear();
    for(int i = 0;i<=max(bestN, bestM);i++)
    {
        toAdd[i].clear();
        cnt2Columns[i].clear();
    }
    for(int j = 0;j<bestM;j++)
    {
        cnt2Columns[0].push_back(j);
    }

    for(int row = 0;row<=bestRows;row++)
    {
        /*
        for(int cnt = 0;cnt<=row;cnt++)
        {
            cout << cnt << ":";
            for(int x: cnt2Columns[cnt]) cout << " " << x;
            cout << '\n';
        }
        cout << " ---- --- --- " << '\n';
        */

        int toFill = bestM/2 + 1;
        for(int i = 0;i<ruined.size();i++)
        {
            toFill--;
            matrix[row][ ruined[i] ] = 1;

            if(toFill==0) break;
        }

        for(int cnt = 0;cnt<=row;cnt++)
        {
            while(toFill>0 && cnt2Columns[cnt].empty()==false)
            {
                matrix[row][ cnt2Columns[cnt].back() ] = 1;
                toAdd[cnt+1].push_back(cnt2Columns[cnt].back());

                toFill--;
                cnt2Columns[cnt].pop_back();
            }
        }
        for(int cnt = 0;cnt<=(bestN-1)/2;cnt++)
        {
            while(toAdd[cnt].empty()==false)
            {
                cnt2Columns[cnt].push_back(toAdd[cnt].back());
                toAdd[cnt].pop_back();
            }
        }
        while(toAdd[(bestN+1)/2].empty()==false)
        {
            ruined.push_back(toAdd[(bestN+1)/2].back());
            toAdd[(bestN+1)/2].pop_back();
        }

        int curr = row + 1;
        for(int cnt = 0;cnt<=(bestN-1)/2;cnt++)
        {
            curr += cnt2Columns[cnt].size();
        }
    }
}

int main()
{
    int T;
    cin >> T;

    while(T--)
    {
        answer = 0;
        memset(matrix, 0, sizeof(matrix));

        cin >> n >> m;

        myCalc(n, m);
        myCalc(m, n);
        recover();

        cout << answer + 69 << '\n';
        for(int i = 0;i<n;i++)
        {
            for(int j = 0;j<m;j++)
            {
                cout << ((matrix[i][j]==1)?'+':'-');
            }
            cout << '\n';
        }
    }
}

Compilation message (stderr)

stones.cpp: In function 'int myCalc(int, int)':
stones.cpp:107:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0;i<ruined.size();i++)
                       ~^~~~~~~~~~~~~~
stones.cpp: In function 'int recover()':
stones.cpp:182:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0;i<ruined.size();i++)
                       ~^~~~~~~~~~~~~~
stones.cpp:221:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

• Subtask 1: 0 / 17
• Subtask 2: 0 / 10
• Subtask 3: 0 / 16
• Subtask 4: 0 / 11
• Subtask 5: 0 / 15
• Subtask 6: 0 / 31