| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 968673 | 2024-04-23T20:01:41 Z | JanDalhuysen | Sails (IOI07_sails) | C++17 | 1000 ms | 65536 KB |
#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
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 348 KB | Output is correct |
| 2 | Correct | 0 ms | 348 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 348 KB | Output is correct |
| 2 | Correct | 1 ms | 436 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 348 KB | Output is correct |
| 2 | Correct | 0 ms | 348 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 314 ms | 604 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Execution timed out | 1025 ms | 27584 KB | Time limit exceeded |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 196 ms | 65536 KB | Execution killed with signal 9 |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Execution timed out | 1033 ms | 2324 KB | Time limit exceeded |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Execution timed out | 1018 ms | 3596 KB | Time limit exceeded |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Execution timed out | 1058 ms | 6404 KB | Time limit exceeded |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Execution timed out | 1082 ms | 6460 KB | Time limit exceeded |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Execution timed out | 1020 ms | 7172 KB | Time limit exceeded |
| 2 | Halted | 0 ms | 0 KB | - |