| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1034075 |
2024-07-25T09:29:55 Z |
김은성(#10970) |
Tiles (BOI24_tiles) |
C++17 |
|
2000 ms |
29620 KB |
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef long long ll;
int a[1009][1009], b[1009][1009];
bool impos[1009];
int orgx[600009];
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);
}
vector<pair<pair<int, bool>, bool> > edge[600009];
int main(){
int n, xm, ym = 1000, i, j;
scanf("%d %d", &n, &xm);
vector<pair<int, int> > p(n), p1(n);
vector<pair<int, int> > xg, yg;
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));
}
p1= p;
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]);
for(i=0; i<n; i++){
xg[i].second = n-1-xg[i].second;
yg[i].second = n-1-yg[i].second;
}
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<=600006; i++)
orgx[i] = i;
int prev_orgg = -1;
for(i=0; i<n; i++){
int orgg = xg[i+1].first, now = xg[i+1].first;
if(xg[i+1].first - xg[i].first >= 4 || prev_orgg == orgg){
int d = (xg[i+1].first - xg[i].first - 2) / 2 * 2;
int temp = xg[i+1].first - (xg[i+1].first - xg[i].first - 2) / 2 * 2;
if(prev_orgg == orgg)
temp = xg[i].first;
orgx[temp] = xg[i+1].first;
now = temp;
xg[i+1].first = temp;
//printf("orgg=%d temp=%d\n", orgg, temp);
if(xg[i+1].second != -1)
p[xg[i+1].second].x = temp;
}
else
orgx[xg[i+1].first] = xg[i+1].first;
for(int x=prev+1; x<=now; x++){
orgx[x] = orgg- (now-x);
//printf("orgx[%d]=%d\n", x, orgx[x]);
}
prev_orgg = orgg;
//printf("prev=%d now=%d\n", prev, now);
prev = now;
}
xm = xg.back().first;
prev_orgg = -1;
for(i=0; i<n; i++){
int orgg = yg[i+1].first;
if(yg[i+1].first - yg[i].first >= 4 || prev_orgg == orgg){
int temp = yg[i+1].first - (yg[i+1].first - yg[i].first - 2) / 2 * 2;
if(prev_orgg == orgg)
temp = yg[i].first;
yg[i+1].first = temp;
p[yg[i+1].second].y = temp;
}
prev_orgg = orgg;
}
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){
edge[x1].push_back(make_pair(make_pair(y1, 0), 0));
edge[x2].push_back(make_pair(make_pair(y1, 0), 1));
}
else{
edge[x2].push_back(make_pair(make_pair(y1, 1), 0));
edge[x1].push_back(make_pair(make_pair(y1, 1), 1));
}
}
}
multiset<pair<int, bool> > st;
bool flag = 0;
int opt = 0;
for(i=0; i<=600007; i++){
sort(edge[i].begin(), edge[i].end());
for(int j=0; j<edge[i].size(); j++){
if(edge[i][j].second == 0)
st.erase(st.find(edge[i][j].first));
else{
auto it = st.insert(edge[i][j].first);
int val = edge[i][j].first.first;
if(edge[i][j].first.second == 1){
if(it!=st.begin()){
it--;
if((val-it->first)%2 == 0)
continue;
flag = 1;
break;
}
}
else{
it++;
if(it!=st.end()){
if((val-it->first)%2 == 0)
continue;
flag = 1;
break;
}
}
}
}
if(flag){
opt = i;
}
}
opt = min(opt, xm);
printf("%d\n", orgx[opt]);
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:46:17: warning: unused variable 'd' [-Wunused-variable]
46 | int d = (xg[i+1].first - xg[i].first - 2) / 2 * 2;
| ^
Main.cpp:99:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, bool>, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for(int j=0; j<edge[i].size(); j++){
| ~^~~~~~~~~~~~~~~
Main.cpp:14:16: warning: unused variable 'ym' [-Wunused-variable]
14 | int n, xm, ym = 1000, i, j;
| ^~
Main.cpp:14:30: warning: unused variable 'j' [-Wunused-variable]
14 | int n, xm, ym = 1000, i, j;
| ^
Main.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
15 | scanf("%d %d", &n, &xm);
| ~~~~~^~~~~~~~~~~~~~~~~~
Main.cpp:19:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
19 | scanf("%d %d", &p[i].x, &p[i].y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2028 ms |
16732 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2028 ms |
16732 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2063 ms |
16984 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2040 ms |
16728 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2016 ms |
16728 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2029 ms |
29620 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2028 ms |
16732 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
