Submission #289128

#	Time	Username	Problem	Language	Result	Execution time	Memory
289128		Pajaraja	별자리 (JOI12_constellation)	C++17	100 / 100	79 ms	16120 KiB

constellation

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10