oj.uz

Submission #289128

# Submission time Handle Problem Language Result Execution time Memory
289128 2020-09-02T11:46:24 Z Pajaraja None (JOI12_constellation) C++17
100 / 100
 79 ms 16120 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxi = 2e5+10;
const long long mo = 1e9+7;
#define pb push_back
struct Point
{
    long long x;
    long long y;
    int z;
};
Point a[maxi];
Point root;
vector<Point> st;
long long dp[3][3][3][maxi];
int belih;
int n;
long long turn(Point a, Point b, Point c) {
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool cmp(Point a, Point b) {
    return turn(root,a,b)>0;
}
void convex()
{
    root = a[1];
    for (int i = 2; i<=n; i++)
        if (a[i].x < root.x || (a[i].x == root.x && a[i].y < root.y))
        {
            swap(a[1], a[i]);
            root = a[1];
        }
    sort(a+2, a+n +1, cmp);
    st.resize(n);
    st[0] = a[1];
    st[1] = a[2];
    int sz = 2;
    for (int i = 3; i<=n; i++)
    {
        while(sz > 1 && turn(st[sz-2],st[sz-1],a[i])<0) sz--;
        st[sz++] = a[i];
    }
    if (st[0].z == 0)
    {
        dp[0][1][1][0] = 1;
        dp[0][2][2][0] = 1;
    }
    else
        dp[0][st[0].z][st[0].z][0] = 1;
    for (int i = 0; i<sz; i++)
        if (st[i].z == 0) belih --;
    for (int i = 1; i<sz; i++)
    {
        if (st[i].z == 0 || st[i].z == 1)
        {
            for (int k = 0; k<=2; k++)
                for (int l = 1; l<=2; l++)
                    for (int o = 1; o<=2; o++)
                    {
                        int poz = k;
                        if (o == 2) poz++;

                        if (poz<=2)
                        {
                            dp[poz][l][1][i] =  (dp[poz][l][1][i] + dp[k][l][o][i-1])%mo;
                        }
                    }
        }
        if (st[i].z == 0 || st[i].z == 2)
        {
            for (int k = 0; k<=2; k++)
                for (int l = 1; l<=2; l++)
                    for (int o = 1; o<=2; o++)
                    {
                        int poz = k;
                        if (o == 1) poz++;

                        if (poz<=2)
                        {
                            dp[poz][l][2][i] =  (dp[poz][l][2][i] + dp[k][l][o][i-1])%mo;

                        }

                     }
        }

    }
    long long ans = 0;
    sz--;
    for (int i = 1;i<=2;i++)
        for (int j = 1;j<=2;j++)
          ans+=dp[0][i][j][sz] + dp[1][i][j][sz];
    ans+=dp[2][1][1][sz] + dp[2][2][2][sz];
    ans%=mo;
    for (int i = 1; i<=belih; i++)
        ans = (ans*2)%mo;
     int ok = 1;
    for (int i = 1;i<=n;i++)
        if (a[i].z == 1) ok = 0;
    ans-=ok;
    ok = 1;
    for (int i = 1;i<=n;i++)
        if (a[i].z == 2) ok = 0;
   ans-=ok;
   if (ans<0) ans+=mo;
    printf("%lld\n", ans);
}
int main()
{
    scanf("%d",&n);
    for (int i = 1; i<=n; i++)
    {
        scanf("%lld%lld%d",&a[i].x,&a[i].y, &a[i].z);
        if (!a[i].z) belih++;
    }
    convex();
}

Compilation message

constellation.cpp: In function 'int main()':
constellation.cpp:110:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  110 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
constellation.cpp:113:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  113 |         scanf("%lld%lld%d",&a[i].x,&a[i].y, &a[i].z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 4 ms 1152 KB Output is correct
3 Correct 5 ms 1152 KB Output is correct
4 Correct 5 ms 1152 KB Output is correct
5 Correct 4 ms 768 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 4 ms 768 KB Output is correct
8 Correct 4 ms 768 KB Output is correct
9 Correct 4 ms 1152 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 68 ms 7288 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 69 ms 7288 KB Output is correct
5 Correct 76 ms 16120 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 4 ms 1152 KB Output is correct
8 Correct 4 ms 1152 KB Output is correct
9 Correct 4 ms 1152 KB Output is correct
10 Correct 76 ms 16120 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 69 ms 7288 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 68 ms 7288 KB Output is correct
5 Correct 75 ms 16120 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 4 ms 1152 KB Output is correct
8 Correct 4 ms 1152 KB Output is correct
9 Correct 4 ms 1152 KB Output is correct
10 Correct 76 ms 16120 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 68 ms 7292 KB Output is correct
3 Correct 76 ms 16120 KB Output is correct
4 Correct 78 ms 15992 KB Output is correct
5 Correct 75 ms 15992 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 4 ms 1152 KB Output is correct
8 Correct 4 ms 1152 KB Output is correct
9 Correct 4 ms 1152 KB Output is correct
10 Correct 74 ms 16096 KB Output is correct
11 Correct 76 ms 16084 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 68 ms 7288 KB Output is correct
3 Correct 68 ms 7288 KB Output is correct
4 Correct 75 ms 15992 KB Output is correct
5 Correct 79 ms 15992 KB Output is correct
6 Correct 76 ms 16120 KB Output is correct
7 Correct 4 ms 1152 KB Output is correct
8 Correct 4 ms 1152 KB Output is correct
9 Correct 5 ms 1152 KB Output is correct
10 Correct 31 ms 8056 KB Output is correct