oj.uz

Submission #1033941

# Submission time Handle Problem Language Result Execution time Memory
1033941 2024-07-25T07:59:29 Z 김은성(#10970) Tiles (BOI24_tiles) C++17
13 / 100
 65 ms 29844 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];
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);
}
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;
    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]);
            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){
            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){
            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;
        //printf("(%d, %d)\n", p[i].first, p[i].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:44:17: warning: unused variable 'd' [-Wunused-variable]
   44 |             int d = (xg[i+1].first - xg[i].first - 2) / 2 * 2;
      |                 ^
Main.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     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);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6744 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 1 ms 6748 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct
9 Correct 1 ms 6748 KB Output is correct
10 Correct 1 ms 6748 KB Output is correct
11 Correct 1 ms 6748 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6744 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 1 ms 6748 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct
9 Correct 1 ms 6748 KB Output is correct
10 Correct 1 ms 6748 KB Output is correct
11 Correct 1 ms 6748 KB Output is correct
12 Correct 1 ms 6748 KB Output is correct
13 Correct 1 ms 6748 KB Output is correct
14 Correct 1 ms 6748 KB Output is correct
15 Correct 1 ms 6748 KB Output is correct
16 Correct 1 ms 6748 KB Output is correct
17 Correct 1 ms 6748 KB Output is correct
18 Correct 1 ms 6744 KB Output is correct
19 Correct 1 ms 6748 KB Output is correct
20 Correct 1 ms 6744 KB Output is correct
21 Correct 1 ms 6748 KB Output is correct
22 Correct 1 ms 6748 KB Output is correct
23 Correct 1 ms 6748 KB Output is correct
24 Correct 1 ms 6748 KB Output is correct
25 Correct 1 ms 6748 KB Output is correct
26 Correct 1 ms 6748 KB Output is correct
27 Correct 1 ms 6744 KB Output is correct
28 Correct 1 ms 6748 KB Output is correct
29 Correct 2 ms 6748 KB Output is correct
30 Correct 1 ms 6760 KB Output is correct
31 Correct 1 ms 6748 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 10588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Incorrect 8 ms 10528 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Runtime error 49 ms 24252 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 65 ms 29844 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6744 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 1 ms 6748 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct
9 Correct 1 ms 6748 KB Output is correct
10 Correct 1 ms 6748 KB Output is correct
11 Correct 1 ms 6748 KB Output is correct
12 Correct 1 ms 6748 KB Output is correct
13 Correct 1 ms 6748 KB Output is correct
14 Correct 1 ms 6748 KB Output is correct
15 Correct 1 ms 6748 KB Output is correct
16 Correct 1 ms 6748 KB Output is correct
17 Correct 1 ms 6748 KB Output is correct
18 Correct 1 ms 6744 KB Output is correct
19 Correct 1 ms 6748 KB Output is correct
20 Correct 1 ms 6744 KB Output is correct
21 Correct 1 ms 6748 KB Output is correct
22 Correct 1 ms 6748 KB Output is correct
23 Correct 1 ms 6748 KB Output is correct
24 Correct 1 ms 6748 KB Output is correct
25 Correct 1 ms 6748 KB Output is correct
26 Correct 1 ms 6748 KB Output is correct
27 Correct 1 ms 6744 KB Output is correct
28 Correct 1 ms 6748 KB Output is correct
29 Correct 2 ms 6748 KB Output is correct
30 Correct 1 ms 6760 KB Output is correct
31 Correct 1 ms 6748 KB Output is correct
32 Incorrect 8 ms 10588 KB Output isn't correct
33 Halted 0 ms 0 KB -