| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1033895 |
2024-07-25T07:38:27 Z |
김은성(#10970) |
Tiles (BOI24_tiles) |
C++17 |
|
68 ms |
29548 KB |
#define x first
#define y second
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[1009][1009], b[1009][1009];
bool impos[1009];
ll ccw(pair<ll, ll> p, pair<ll, ll> q, pair<ll, ll> r){
return (q.x-p.x)*(r.y-p.y) + (r.x-p.x)*(q.y-p.y);
}
int main(){
int n, xm, ym = 1000, i, j;
scanf("%d %d", &n, &xm);
vector<pair<int, int> > p(n);
vector<pair<int, int> > xg, yg;
unordered_map<int, int> orgx;
for(i=0; i<n; i++){
scanf("%d %d", &p[i].x, &p[i].y);
xg.push_back(make_pair(p[i].x, i));
yg.push_back(make_pair(p[i].y, i));
}
for(i=0; i<n; i++){
if(ccw(p[i], p[(i+1)%n], p[(i+2)%n]) < 0){
for(i=0; i<n/2; i++)
swap(p[i], p[n-1-i]);
break;
}
}
xg.push_back(make_pair(0, -1));
yg.push_back(make_pair(0, -1));
sort(xg.begin(), xg.end());
sort(yg.begin(), yg.end());
int prev = -1;
for(i=0; i<n; i++){
int now = xg[i+1].first;
if(xg[i+1].first - xg[i].first >= 3){
int d = (xg[i+1].first - xg[i].first - 1) / 2 * 2;
int temp = xg[i+1].first - (xg[i+1].first - xg[i].first - 1) / 2 * 2;
orgx[temp] = xg[i+1].first;
now = temp;
xg[i+1].first = temp;
p[xg[i+1].second].x = temp;
if(prev!=-1)
orgx[prev] += d;
}
else
orgx[xg[i+1].first] = xg[i+1].first;
prev = now;
}
xm = xg.back().first;
for(i=0; i<n; i++){
if(yg[i+1].first - yg[i].first >= 3){
int temp = yg[i+1].first - (yg[i+1].first - yg[i].first - 1) / 2 * 2;
yg[i+1].first = temp;
p[yg[i+1].second].y = temp;
}
}
for(i=0; i<n; i++){
int x1 = p[i].first, y1 = p[i].second;
int x2 = p[(i+1)%n].first, y2 = p[(i+1)%n].second;
if(y1 == y2){
if(x1 < x2){
for(j=x1; j<x2; j++)
a[j][y1]--;
}
else{
for(j=x1-1; j>=x2; j--)
a[j][y2]++;
}
}
}
for(i=0; i<=xm; i++){
for(j=0; j<=ym; j++){
a[i][j] += (j==0 ? 0 : a[i][j-1]);
//printf("%d", a[i][j]);
b[i][j] = a[i][j];
}
//printf("\n");
}
bool flag = 0;
for(i=0; i<=ym; i++){
int cur = 0;
bool flag = 0;
for(j=0; j<=xm; j++){
if(!a[j][i]){
if(cur%2==1)
flag = 1;
cur = 0;
}
else
cur++;
if(flag || cur%2)
impos[j] = 1;
if(cur%2)
b[j+1][i] = 0;
}
}
for(i=0; i<=xm; i++){
int cur = 0;
for(j=0; j<=ym; j++){
if(!b[i][j]){
if(cur%2 == 1){
flag = 1;
break;
}
cur = 0;
}
else
cur++;
}
if(flag)
impos[i] = 1;
}
int opt = 0;
for(i=0; i<xm; i++){
if(!impos[i])
opt = i+1;
}
printf("%d\n", orgx[opt]);
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.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, &xm);
| ~~~~~^~~~~~~~~~~~~~~~~~
Main.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
18 | scanf("%d %d", &p[i].x, &p[i].y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
8284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
11 ms |
8416 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
68 ms |
29548 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
