Submission #160746

#	Time	Username	Problem	Language	Result	Execution time	Memory
160746		stoyan_malinin	Red-blue table (IZhO19_stones)	C++14	100 / 100	93 ms	5444 KiB

stones

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

using namespace std;

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];

bool bestMode;
int bestN, bestM, bestRows;

bool matrix[1005][1005];

int myCalc(int n, int m, bool mode)
{
    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);
    }

    //cout << answer << " vs " << m << '\n';
    if(answer < m)
    {
        answer = m;

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

    for(int row = 0;row<n;row++)
    {
        /*
        cout << "ruined:";
        for(int x: ruined) cout << " " << x;
        cout << '\n';
        for(int cnt = 0;cnt<=(n-1)/2;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<=(n-1)/2;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();
        }

        //cout << answer << " vs " << curr << '\n';
        if(answer < curr)
        {
            answer = curr;

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

    return answer;
}

int n, m;
int recover()
{
    if(bestMode==true)
    {
        for(int i = 0;i<n;i++)
        {
            for(int j = 0;j<m;j++)
            {
                matrix[i][j] = 1;
            }
        }
    }

    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++)
    {
        int toFill = bestM/2 + 1;
        for(int i = 0;i<ruined.size();i++)
        {
            toFill--;
            if(bestMode==false) matrix[row][ ruined[i] ] = 1;
            else matrix[ ruined[i] ][row] = 0;

            if(toFill==0) break;
        }

        for(int cnt = 0;cnt<=(bestN-1)/2;cnt++)
        {
            while(toFill>0 && cnt2Columns[cnt].empty()==false)
            {
                if(bestMode==false) matrix[row][ cnt2Columns[cnt].back() ] = 1;
                else matrix[ cnt2Columns[cnt].back() ][row] = 0;

                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, false);
        myCalc(m, n, true);
        recover();

            //cout << n << " &&&&&& " << m << '\n';
            //cout << answer << " -> " << bestN << " " << bestM << " " << bestRows << '\n';

        cout << answer << '\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, bool)':
stones.cpp:114: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:193:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0;i<ruined.size();i++)
                       ~^~~~~~~~~~~~~~
stones.cpp:235:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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