oj.uz

Submission #594869

# Submission time Handle Problem Language Result Execution time Memory
594869 2022-07-13T05:42:09 Z 박상훈(#8436) Dragon 2 (JOI17_dragon2) C++17
15 / 100
 4000 ms 4392 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

struct Point;
ll xo, yo;
int ccw(Point a, Point b, Point c);

struct Point{
    ll x, y, i;
    Point(){}
    Point(ll _x, ll _y, ll _i): x(_x), y(_y), i(_i) {}

    bool operator<(const Point &P) const{
        bool left1 = (x-xo<0 || (x-xo==0 && y-yo>0));
        bool left2 = (P.x-xo<0 || (P.x-xo==0 && P.y-yo>0));
        if (left1!=left2) return left1 > left2;

        return ccw(Point(xo, yo, 0), *this, P) > 0;
    }
}a[60060], b[60060], O1, O2;
int n, c[30030], nx[30030], ny[30030];
vector<int> T[30030];

int ccw(Point a, Point b, Point c){
    ll ret = (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
    if (ret>0) return 1;
    if (ret<0) return -1;
    return 0;
}

ll calc(int c1, int c2){
    ll ret = 0;
    for (auto &i:T[c1]){
        int sx = nx[i], sy = ny[i];
        for (int j=sx+1;j<sx+n;j++){
            if (ccw(a[sx], O1, O2)!=ccw(a[sx], O1, a[j])) continue;
            if (ccw(b[sy], O2, O1)!=ccw(b[sy], O2, a[j])) continue;
            if (c[a[j].i]!=c2) continue;
            //printf("ok: %lld %lld %lld %lld (j = %d / %lld %lld)\n", a[sx].x, a[sx].y, a[j].x, a[j].y, j, b[sy].x, b[sy].y);
            ret++;
        }
    }
    return ret;
}

void init(Point O, Point a[], int nx[]){
    xo = O.x, yo = O.y;
    sort(a+1, a+n+1);
    for (int i=n+1;i<=n*2;i++) a[i] = a[i-n];

    for (int i=1;i<=n;i++) nx[a[i].i] = i;
}

int main(){
    int m;
    scanf("%d %d", &n, &m);
    for (int i=1;i<=n;i++){
        scanf("%lld %lld %d", &a[i].x, &a[i].y, c+i);
        a[i].i = i;
        b[i] = a[i];
        T[c[i]].push_back(i);
    }

    scanf("%lld %lld %lld %lld", &O1.x, &O1.y, &O2.x, &O2.y);
    init(O1, a, nx);
    init(O2, b, ny);

    int q;
    scanf("%d", &q);
    while(q--){
        int c1, c2;
        scanf("%d %d", &c1, &c2);
        printf("%lld\n", calc(c1, c2));
    }
    return 0;
}

Compilation message

dragon2.cpp: In function 'int main()':
dragon2.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
dragon2.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         scanf("%lld %lld %d", &a[i].x, &a[i].y, c+i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |     scanf("%lld %lld %lld %lld", &O1.x, &O1.y, &O2.x, &O2.y);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
dragon2.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         scanf("%d %d", &c1, &c2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1364 KB Output is correct
2 Correct 167 ms 1492 KB Output is correct
3 Correct 1606 ms 1364 KB Output is correct
4 Correct 2479 ms 1688 KB Output is correct
5 Correct 1014 ms 1516 KB Output is correct
6 Correct 12 ms 1364 KB Output is correct
7 Correct 11 ms 1364 KB Output is correct
8 Correct 16 ms 1364 KB Output is correct
9 Correct 15 ms 1368 KB Output is correct
10 Correct 15 ms 1372 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3093 ms 4392 KB Output is correct
2 Execution timed out 4081 ms 4360 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1364 KB Output is correct
2 Correct 167 ms 1492 KB Output is correct
3 Correct 1606 ms 1364 KB Output is correct
4 Correct 2479 ms 1688 KB Output is correct
5 Correct 1014 ms 1516 KB Output is correct
6 Correct 12 ms 1364 KB Output is correct
7 Correct 11 ms 1364 KB Output is correct
8 Correct 16 ms 1364 KB Output is correct
9 Correct 15 ms 1368 KB Output is correct
10 Correct 15 ms 1372 KB Output is correct
11 Correct 3093 ms 4392 KB Output is correct
12 Execution timed out 4081 ms 4360 KB Time limit exceeded
13 Halted 0 ms 0 KB -