Submission #968673

#	Time	Username	Problem	Language	Result	Execution time	Memory
968673		JanDalhuysen	Sails (IOI07_sails)	C++17	25 / 100	1082 ms	65536 KiB

sails

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<vector<int>> grid;

    vector<vector<int>> masts;

    int max_height = 0;

    int flags_remaining = 0;

    int n;
    cin >> n;

    int n_copy = n;

    while(n--)
    {
        int h;
        int k;
        cin >> h >> k;

        flags_remaining += k;

        if (h > max_height)
        {
            max_height = h;
        }

        vector<int> temp;
        temp.push_back(h);
        temp.push_back(k);
        masts.push_back(temp);
    }

    // sort by height

    for (int i = 0; i < masts.size()-1; i++)
    {
        for (int j = 0; j < masts.size()-1; j++)
        {
            if (masts[j][0] > masts[j+1][0])
            {
                int temp_one = 0;
                int temp_two = 0;

                temp_one = masts[j+1][0];
                temp_two = masts[j+1][1];

                masts[j+1][0] = masts[j][0];
                masts[j+1][1] = masts[j][1];

                masts[j][0] = temp_one;
                masts[j][1] = temp_two;
            }
        }
    }

    // sort by flags

    for (int i = 0; i < masts.size()-1; i++)
    {
        for (int j = 0; j < masts.size()-1; j++)
        {
            if ((masts[j][0] == masts[j+1][0]) && (masts[j][1] > masts[j+1][1]))
            {
                int temp_one = 0;
                int temp_two = 0;

                temp_one = masts[j+1][0];
                temp_two = masts[j+1][1];

                masts[j+1][0] = masts[j][0];
                masts[j+1][1] = masts[j][1];

                masts[j][0] = temp_one;
                masts[j][1] = temp_two;
            }
        }
    }

    // make grid with zeros

    for (int i = 0; i < max_height; i++)
    {
        vector<int> temp;
        for (int j = 0; j < n_copy; j++)
        {
            temp.push_back(0);
        }
        grid.push_back(temp);
    }

    // ----------
    // find that what will give you the lowest score in rows => if there are multiple find highest up
    // ----------

    for (int jan = 0; jan < max_height; jan++)
    {
        if (jan == 0)
        {
            // do n_copy times
            for (int mast_number = 0; mast_number < n_copy; mast_number++)
            {
                // check if current mast has flags remaining
                if (masts[mast_number][1] > 0)
                {
                    vector<int> row_totals;
                    // current mast height
                    int current_mast_height = masts[mast_number][0];
                    // find row with lowest score
                    for (int i = 0; i < current_mast_height; i++)
                    {
                        int row_total = 0;
                        for (int j = 0; j < grid[i].size(); j++)
                        {
                            row_total += grid[i][j];
                        }
                        row_totals.push_back(row_total);
                    }
                    // find the lowest values in row_totals
                    int lowest = 9999;
                    for (int i = 0; i < row_totals.size(); i++)
                    {
                        if (row_totals[i] < lowest)
                        {
                            lowest = row_totals[i];
                        }
                    }

                    int stop = 0;

                    for (int i = current_mast_height-1; i > -1; i--)
                    {
                        if (stop == 1)
                        {
                            break;
                        }
                        else if (row_totals[i] == lowest)
                        {
                            // add a flag
                            grid[i][mast_number] = 1;
                            masts[mast_number][1] -= 1;
                            flags_remaining -= 1;
                            stop = 1;
                        }
                    }
                }
            }
        }
        else
        {
            // do n_copy times
            for (int mast_number = 0; mast_number < n_copy; mast_number++)
            {
                // check if current mast has flags remaining
                if (masts[mast_number][1] > 0)
                {
                    vector<int> row_totals;
                    // current mast height
                    int current_mast_height = masts[mast_number][0];
                    // find row with lowest score
                    for (int i = 0; i < current_mast_height; i++)
                    {
                        int row_total = 0;
                        for (int j = 0; j < grid[i].size(); j++)
                        {
                            row_total += grid[i][j];
                        }
                        row_totals.push_back(row_total);
                    }
                    // find the lowest values in row_totals
                    int lowest = 9999;
                    for (int i = 0; i < row_totals.size(); i++)
                    {
                        if (row_totals[i] < lowest)
                        {
                            lowest = row_totals[i];
                        }
                    }

                    int stop = 0;

                    int warning = 0;

                    for (int i = current_mast_height-1; i > -1; i--)
                    {
                        if (stop == 1)
                        {
                            break;
                        }
                        else if (row_totals[i] == lowest)
                        {
                            if (grid[i][mast_number] == 1)
                            {
                                // do nothing
                                // set warning
                                warning = 1;
                            }
                            else
                            {
                                // add a flag
                                grid[i][mast_number] = 1;
                                masts[mast_number][1] -= 1;
                                flags_remaining -= 1;
                                stop = 1;
                                warning = 0;
                            }
                        }
                    }

                    if (warning == 1)
                    {
                        lowest++;
                        for (int i = current_mast_height-1; i > -1; i--)
                        {
                            if (stop == 1)
                            {
                                break;
                            }
                            else if (row_totals[i] == lowest)
                            {
                                if (grid[i][mast_number] == 1)
                                {
                                    // do nothing
                                    // set warning
                                    warning = 1;
                                }
                                else
                                {
                                    // add a flag
                                    grid[i][mast_number] = 1;
                                    masts[mast_number][1] -= 1;
                                    flags_remaining -= 1;
                                    stop = 1;
                                    warning = 0;
                                }
                            }
                        }
                    }

                    if (warning == 1)
                    {
                        lowest++;
                        for (int i = current_mast_height-1; i > -1; i--)
                        {
                            if (stop == 1)
                            {
                                break;
                            }
                            else if (row_totals[i] == lowest)
                            {
                                if (grid[i][mast_number] == 1)
                                {
                                    // do nothing
                                    // set warning
                                    warning = 1;
                                }
                                else
                                {
                                    // add a flag
                                    grid[i][mast_number] = 1;
                                    masts[mast_number][1] -= 1;
                                    flags_remaining -= 1;
                                    stop = 1;
                                    warning = 0;
                                }
                            }
                        }
                    }

                    if (warning == 1)
                    {
                        lowest++;
                        for (int i = current_mast_height-1; i > -1; i--)
                        {
                            if (stop == 1)
                            {
                                break;
                            }
                            else if (row_totals[i] == lowest)
                            {
                                if (grid[i][mast_number] == 1)
                                {
                                    // do nothing
                                    // set warning
                                    warning = 1;
                                }
                                else
                                {
                                    // add a flag
                                    grid[i][mast_number] = 1;
                                    masts[mast_number][1] -= 1;
                                    flags_remaining -= 1;
                                    stop = 1;
                                    warning = 0;
                                }
                            }
                        }
                    }

                    if (warning == 1)
                    {
                        lowest++;
                        for (int i = current_mast_height-1; i > -1; i--)
                        {
                            if (stop == 1)
                            {
                                break;
                            }
                            else if (row_totals[i] == lowest)
                            {
                                if (grid[i][mast_number] == 1)
                                {
                                    // do nothing
                                    // set warning
                                    warning = 1;
                                }
                                else
                                {
                                    // add a flag
                                    grid[i][mast_number] = 1;
                                    masts[mast_number][1] -= 1;
                                    flags_remaining -= 1;
                                    stop = 1;
                                    warning = 0;
                                }
                            }
                        }
                    }

                    if (warning == 1)
                    {
                        lowest++;
                        for (int i = current_mast_height-1; i > -1; i--)
                        {
                            if (stop == 1)
                            {
                                break;
                            }
                            else if (row_totals[i] == lowest)
                            {
                                if (grid[i][mast_number] == 1)
                                {
                                    // do nothing
                                    // set warning
                                    warning = 1;
                                }
                                else
                                {
                                    // add a flag
                                    grid[i][mast_number] = 1;
                                    masts[mast_number][1] -= 1;
                                    flags_remaining -= 1;
                                    stop = 1;
                                    warning = 0;
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    // get the total of each row of the grid
    vector<int> row_totals;
    for (int i = 0; i < grid.size(); i++)
    {
        int row_total = 0;
        for (int j = 0; j < grid[i].size(); j++)
        {
            row_total += grid[i][j];
        }
        row_totals.push_back(row_total);
    }

    int jan_answer = 0;

    for (int i = 0; i < row_totals.size(); i++)
    {
        for (int j = 0; j < row_totals[i]-1; j++)
        {
            jan_answer += j+1;
        }
    }

    cout << jan_answer << endl;
    
}

Compilation message (stderr)

sails.cpp: In function 'int main()':
sails.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int i = 0; i < masts.size()-1; i++)
      |                     ~~^~~~~~~~~~~~~~~~
sails.cpp:44:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for (int j = 0; j < masts.size()-1; j++)
      |                         ~~^~~~~~~~~~~~~~~~
sails.cpp:65:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for (int i = 0; i < masts.size()-1; i++)
      |                     ~~^~~~~~~~~~~~~~~~
sails.cpp:67:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         for (int j = 0; j < masts.size()-1; j++)
      |                         ~~^~~~~~~~~~~~~~~~
sails.cpp:119:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |                         for (int j = 0; j < grid[i].size(); j++)
      |                                         ~~^~~~~~~~~~~~~~~~
sails.cpp:127:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |                     for (int i = 0; i < row_totals.size(); i++)
      |                                     ~~^~~~~~~~~~~~~~~~~~~
sails.cpp:170:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |                         for (int j = 0; j < grid[i].size(); j++)
      |                                         ~~^~~~~~~~~~~~~~~~
sails.cpp:178:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |                     for (int i = 0; i < row_totals.size(); i++)
      |                                     ~~^~~~~~~~~~~~~~~~~~~
sails.cpp:372:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  372 |     for (int i = 0; i < grid.size(); i++)
      |                     ~~^~~~~~~~~~~~~
sails.cpp:375:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  375 |         for (int j = 0; j < grid[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~
sails.cpp:384:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  384 |     for (int i = 0; i < row_totals.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10