oj.uz

Submission #439864

# Submission time Handle Problem Language Result Execution time Memory
439864 2021-07-01T03:48:29 Z 반딧불(#7618) Hexagonal Territory (APIO21_hexagon) C++17
3 / 100
 1 ms 204 KB 
/*#include <bits/stdc++.h>
#include "hexagon.h"

using namespace std;

typedef long long ll;
const ll MOD = 1000000007;
const ll INV2 = 500000004;
const ll INV3 = 333333336;
const int xx[]={0, 1, 1, 0, -1, -1}, yy[]={2, 1, -1, -2, -1, 1};
ll A, B;

namespace basicMath{ /// �⺻���� ����� ����ϴ� �Լ����� ���� �̸������̴�.
    ll sum_1b (ll b){ /// 0���� b������ ������ ���� ��ȯ�Ѵ�.
        return (b * (b+1) % MOD * INV2 % MOD);
    }

    ll sum_ab (ll a, ll b){ /// a���� b������ ������ ���� ��ȯ�Ѵ�.
        return (sum_1b(b) - sum_1b(a-1) + MOD) % MOD;
    }

    ll sum_1b2 (ll b){ /// 0���� b������ ������ ������ ���� ��ȯ�Ѵ�.
        return (b * (b+1) % MOD * (b+b+1) % MOD * INV2 % MOD * INV3 % MOD);
    }

    ll sum_ab2 (ll a, ll b){ /// a���� b������ ������ ������ ���� ��ȯ�Ѵ�.
        return (sum_1b2(b) - sum_1b2(a-1) + MOD) % MOD;
    }

    ll sum_mult(ll s, ll e, ll d, ll l){
        /// �Ա��� �β��� s, �ⱸ�� �β��� e�̴�.
        /// �Ա��� �ⱸ ������ �Ÿ��� l�̰�, �������� �Ա� ������ �Ÿ��� d�̴�.
        ll numberOfPoints = 0; /// ���� ������, ���⿡ A�� ���ؾ� �Ѵ�.
        ll distanceSum = 0; /// �Ÿ� ������, ���⿡ B�� ���ؾ� �Ѵ�.
        if(s < e){ /// �β��� ���� Ŀ���� ��츦 ����Ѵ�.
            numberOfPoints = sum_ab(s+1, e-1);
            distanceSum = (sum_ab2(s+1, e-1) + (d-s)*sum_ab(s+1, e-1)%MOD + MOD) % MOD;
        }
        else if(s == e){ /// �β��� ������ ��츦 ����Ѵ�.
            numberOfPoints = (l-1) * s % MOD;
            distanceSum = sum_ab(d+1, d+l-1);
        }
        else{
            numberOfPoints = sum_ab(e+1, s-1);
            distanceSum = (s*s%MOD*(s-e-1)%MOD - sum_1b2(s-e+1)%MOD + (d-s)*sum_ab(e+1, s-1)%MOD + MOD + MOD) % MOD;
        }
        return (A * numberOfPoints + B * distanceSum) % MOD;
    }
}
using namespace basicMath;

namespace Calculator{
    struct Node { /// Ʈ���� ��� ����ü�� �����Ѵ�.
        ll weight; /// ����� ����ġ (�ش� ���� ���� �����ϴ� �� ����)�� �����Ѵ�.
        struct Edge{ /// Ʈ���� ���� ����ü�� �����Ѵ�.
            Node* cur; /// ���� ������ �ǹ��ϴ� ��� ������ �����̴�.
            Node* nxt; /// ��ǥ ������ �ǹ��ϴ� ��� ������ �����̴�.
            ll slope;  /// ������ �β� ��ȭ�� �ǹ��ϴ� �����̴�.
            ll len;    /// ������ ���̸� �ǹ��ϴ� �����̴�.

            Edge(Node* cur, Node* nxt, ll slope, ll len): cur(cur), nxt(nxt), slope(slope), len(len){} /// ������ �������̴�.
        };
        vector<Edge> link; /// Ʈ�� ����� ���� ����Ʈ�̴�.

        Node(ll weight): weight(weight){} /// ����� �������̴�.

        ll calculateAnswer(Node* prv = nullptr, ll dist = 0){ /// Ʈ�� ������ dfs�� ���� ���� ����ϴ� �Լ��̴�.
            ll returnValue = (A * weight % MOD + B * dist % MOD * weight % MOD) % MOD;
            for(Edge edge: link){ /// ���� �������� ��ȸ�Ѵ�.
                if(edge.nxt == prv) continue; /// �̹� �湮�� ������ �湮���� �ʴ´�.
                if(edge.len >= 2){
                    returnValue += sum_mult(weight, edge.nxt->weight, dist, edge.len); /// ���� ������ ���� �����Ѵ�.
                    returnValue %= MOD;
                }
                returnValue += edge.nxt->calculateAnswer(this, dist + edge.len); /// ���� �������� �̵��Ѵ�.
                returnValue %= MOD;
            }
            return returnValue; /// ���� ��ȯ�Ѵ�.
        }
    };

    vector<Node*> makeTree(int N, vector<int> D, vector<int> L){ /// Ʈ���� �����ϴ� �Լ��̴�.
        Node* node1 = new Node(1);
        Node* node2 = new Node(L[0]+1);
        node1->link.push_back(Node::Edge(node1, node2, 1, L[0]));
        node2->link.push_back(Node::Edge(node2, node1, -1, L[0]));
        if(D[0] % 3) swap(node1, node2);
        return vector<Node*> {node1, node2};
    }

    ll calc(int N, vector<int> D, vector<int> L){
        /// Ǯ�̴� ũ�� �� �ܰ�� ���� �� �ִ�.
        /// ù ��° �ܰ�: Ʈ���� �����ϱ�
        /// �� ��° �ܰ�: Ʈ�� ������ Ʈ�� DP�� �����ؼ� ������ ���

        vector<Node*> nodeList = makeTree(N, D, L);      /// Ʈ���� �����Ѵ�.
        ll returnValue = nodeList[0]->calculateAnswer(); /// Ʈ�� ������ ���� ����Ѵ�.

        for(Node* pnt: nodeList){ /// ����� �޸𸮸� ������ �ش�.
            delete pnt;
        }
        return returnValue; /// ���� ��ȯ�Ѵ�.
    }
}

int draw_territory(int N, int _A, int _B, vector<int> D, vector<int> L){
    A = _A * 2 * INV3 % MOD, B = _B;
    for(int i=0; i<N; i++) D[i]--;
    ll Answer = 0;
    Answer += Calculator::calc(N, D, L);
    for(int i=0; i<N; i++) D[i] = (D[i] + 1) % 6;
    Answer += Calculator::calc(N, D, L);
    for(int i=0; i<N; i++) D[i] = (D[i] + 1) % 6;
    Answer += Calculator::calc(N, D, L);
    Answer %= MOD;
    Answer *= INV2;
    Answer %= MOD;
    return Answer;
}

*/

#include <bits/stdc++.h>
#include "hexagon.h"

using namespace std;

typedef long long ll;
const ll MOD = 1000000007;
int xx[]={0, 1, 1, 0, -1, -1}, yy[]={2, 1, -1, -2, -1, 1};

int n;
ll A, B;
ll ans = 0;

struct Line{
    ll a, b;
};



ll calculate(vector<int> D, vector<int> L){
    ll x = 0, y = 0;
    for(int i=0; i<n; i++){
        ll sx = x, sy = y;
        ll ex = x+L[i]*xx[D[i]], ey = y+L[i]*yy[D[i]];

    }
}

int draw_territory(int N, int _A, int _B, vector<int> D, vector<int> L) {
    n = N;
    A = _A, B = _B;

    ll ans = 0;
    ll l = L[0];
    ans += (l+1) * (l+2) / 2 % MOD * (A+B) % MOD;
    ans += l * (l+1) / 2 % MOD * (l+l+1) % MOD * 333333336 % MOD * B % MOD;
    return ans%MOD;


    ll an = 0;
    an += calculate(D, L);
    for(int i=0; i<n; i++) D[i] = D[i] % 6 + 1;
    an += calculate(D, L);
    for(int i=0; i<n; i++) D[i] = D[i] % 6 + 1;
    an += calculate(D, L);

    return an % MOD;
}

Compilation message

hexagon.cpp: In function 'll calculate(std::vector<int>, std::vector<int>)':
hexagon.cpp:145:12: warning: unused variable 'sx' [-Wunused-variable]
  145 |         ll sx = x, sy = y;
      |            ^~
hexagon.cpp:145:20: warning: unused variable 'sy' [-Wunused-variable]
  145 |         ll sx = x, sy = y;
      |                    ^~
hexagon.cpp:146:12: warning: unused variable 'ex' [-Wunused-variable]
  146 |         ll ex = x+L[i]*xx[D[i]], ey = y+L[i]*yy[D[i]];
      |            ^~
hexagon.cpp:146:34: warning: unused variable 'ey' [-Wunused-variable]
  146 |         ll ex = x+L[i]*xx[D[i]], ey = y+L[i]*yy[D[i]];
      |                                  ^~
hexagon.cpp:149:1: warning: no return statement in function returning non-void [-Wreturn-type]
  149 | }
      | ^

Subtask #1
3.0 / 3.0

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

Subtask #2
0 / 6.0

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

Subtask #3
0 / 11.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 15.0

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

Subtask #6
0 / 19.0

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

Subtask #7
0 / 18.0

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

Subtask #8
0 / 16.0

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