Code Submission Evaluation System Login

BOI 2016, day 1

Start:2016-05-12 09:00:00
End:2016-05-12 14:00:00
 

Tasks | Scoreboard | Statistics


CSES - BOI 2016, day 1 - Results
History
2016-05-12 13:36:18100
2016-05-12 13:34:54100
2016-05-12 13:21:2931
2016-05-12 13:05:1758
2016-05-12 13:04:4746
2016-05-12 13:01:4146
2016-05-12 11:30:4215
2016-05-12 11:19:480
2016-05-12 11:18:110
2016-05-12 11:17:360
2016-05-12 11:16:400
2016-05-12 10:51:4827
2016-05-12 10:48:3512
2016-05-12 10:43:4112
2016-05-12 10:40:050
2016-05-12 10:34:3912
2016-05-12 10:29:200
Task:Spiral
Sender:dbradac
Submission time:2016-05-12 13:36:18
Language:C++
Status:READY
Score:100

Feedback

groupverdictscore
#1ACCEPTED12
#2ACCEPTED15
#3ACCEPTED17
#4ACCEPTED31
#5ACCEPTED25

Test results

testverdicttime (s)group
#1ACCEPTED0.07 / 1.501details
#2ACCEPTED0.05 / 1.502details
#3ACCEPTED0.06 / 1.503details
#4ACCEPTED0.06 / 1.504details
#5ACCEPTED0.06 / 1.505details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:264:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &n, &brq);
                          ^
input/code.cpp:290:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
                                          ^

Code

#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

#define TRACE(x) cerr << #x << " = " << x << endl

typedef long long ll;
typedef pair <ll, ll> P;
#define X first
#define Y second

const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;

ll Add(ll a, ll b)
{
  return ((a + b) % MOD + MOD) % MOD;
}

ll Sub(ll a, ll b)
{
  return ((a - b) % MOD + MOD) % MOD;
}

ll Mul(ll a, ll b)
{
  return (a * b) % MOD;
}

ll Sq(ll x)
{
  return Mul(x, x);
}

ll Eksp(ll b, ll e)
{
  ll ret = 1;
  for (; e; e/=2, b=Mul(b, b))
    if (e & 1)
      ret = Mul(ret, b);

  return ret;
}

ll Div(ll a, ll b)
{
  assert(b);
  return Mul(a, Eksp(b, MOD-2));
}

ll InterPol(vector <P> V, ll x)
{
  ll ret = 0;
  int n = (int) V.size();

  for (int i=0; i<n; i++) {
    ll um = 1;
    for (int j=0; j<n; j++)
      if (j != i)
        um = Mul(um, Div(Sub(x, V[j].X), Sub(V[i].X, V[j].X)));

    ret = Add(ret, Mul(um, V[i].Y));
  }

  return ret;
}

ll indmal[3][3] = {7, 8, 9, 6, 1, 2, 5, 4, 3};

ll Mali(P poz)
{
  return indmal[poz.Y+1][poz.X+1];
}

P Pomak(P poc, P vec)
{
  return P(poc.X + vec.X, poc.Y + vec.Y);
}

ll Val(P poz)
{
  if (abs(poz.X) < 2 && abs(poz.Y) < 2)
    return Mali(poz);

  if (poz.X == -poz.Y && poz.X > 0)
    return Sq(Add(Mul(2, poz.X), 1));

  ll poc = max(abs(poz.X), abs(poz.Y)) - 1, ret = Add(Sq(Add(Mul(2, poc), 1)), 1);
  P pomaci[4] = { P(0, 2 * poc + 1), P(-2 * (poc + 1), 0), P(0, -2 * (poc + 1)), P(2 * (poc + 1), 0) };
  P tmp = P(poc + 1, -poc);

  for (int i=0; i<4; i++) {
    P nov = Pomak(tmp, pomaci[i]);
    if (poz.X == tmp.X && poz.X == nov.X) {
      ret = Add(ret, abs(poz.Y - tmp.Y));
      return ret;
    }

    if (poz.Y == tmp.Y && poz.Y == nov.Y) {
      ret = Add(ret, abs(poz.X - tmp.X));
      return ret;
    }

    ret = Add(ret, Add(abs(tmp.X - nov.X), abs(tmp.Y - nov.Y)));
    tmp = nov;
  }

  assert(0);
}

ll ValKv(P poz, int stx, int sty)
{
  return Val(P(poz.X * stx, poz.Y * sty));
}

P PresInt(P a, P b)
{
  if (a.X > b.Y || b.X > a.Y)
    return P(-INF, -INF);
  return P(max(a.X, b.X), min(a.Y, b.Y));
}

pair<P, P> Presjek(pair<P, P> a, pair<P, P> b)
{
  P prx = PresInt(P(a.X.X, a.Y.X), P(b.X.X, b.Y.X));
  P pry = PresInt(P(a.X.Y, a.Y.Y), P(b.X.Y, b.Y.Y));

  if (prx == P(-INF, -INF) || pry == P(-INF, -INF))
    return make_pair(P(-INF, -INF), P(-INF, -INF));
  return make_pair(P(prx.X, pry.X), P(prx.Y, pry.Y));
}

int Invalid(pair<P, P> prav)
{
  if (prav.X.X == -INF || prav.X.Y == -INF ||
      prav.Y.X == -INF || prav.Y.Y == -INF)
    return 1;
  return prav.X.X > prav.Y.X || prav.X.Y > prav.Y.Y;
}

ll RijesiKvadrat(P vrh, ll raz, int stx, int sty)
{
  if (raz < 0 || vrh.X <= -INF + 5)
    return 0;

  vector <P> V;
  ll vrij[5];
  memset(vrij, 0, sizeof vrij);

  for (int i=0; i<5; i++) {
    for (int j=0; j<5; j++) {
      ll tmp = ValKv(P(vrh.X + i, vrh.Y + j), stx, sty);
      vrij[max(i, j)] = Add(vrij[max(i, j)], tmp);
    }
  }

  ll dosad = 0;
  for (int i=0; i<5; i++) {
    dosad = Add(dosad, vrij[i]);
    V.push_back(P(i, dosad));
  }

  return InterPol(V, raz);
}

ll RijesiX(ll x, ll y1, ll y2, int stx, int sty)
{
  vector <P> V;
  ll dosad = 0;

  for (int i=0; i<5; i++) {
    ll tmp = ValKv(P(x, y1+i), stx, sty);
    dosad = Add(dosad, tmp);
    V.push_back(P(i, dosad));
  }

  return InterPol(V, y2 - y1);
}

ll RijesiPrazan(pair<P, P> prav, int stx, int sty)
{
  if (Invalid(prav))
    return 0;

  vector <P> V;
  ll dosad = 0;

  for (int i=0; i<5; i++) {
    ll tmp = RijesiX(prav.X.X+i, prav.X.Y, prav.Y.Y, stx, sty);
    dosad = Add(dosad, tmp);
    V.push_back(P(i, dosad));
  }

  return InterPol(V, prav.Y.X - prav.X.X);
}

ll RijesiDijag(pair<P, P> prav, int stx, int sty)
{
  if (Invalid(prav))
    return 0;

  if (prav.Y.X > prav.Y.Y) {
    pair<P, P> des = make_pair(P(prav.Y.Y + 1, prav.X.Y), prav.Y);
    return Add(RijesiPrazan(des, stx, sty), RijesiKvadrat(prav.X, prav.Y.Y - prav.X.Y, stx, sty));
  }
  pair<P, P> gor = make_pair(P(prav.X.X, prav.Y.X + 1), prav.Y);
  return Add(RijesiPrazan(gor, stx, sty), RijesiKvadrat(prav.X, prav.Y.X - prav.X.X, stx, sty));
}

ll RijesiPrvi(pair<P, P> prav, int stx, int sty)
{
  if (Invalid(prav))
    return 0;

  if (prav.X.Y <= prav.X.X) {
    if (prav.Y.Y <= prav.X.X)
      return RijesiPrazan(prav, stx, sty);

    pair<P, P> dol = make_pair(prav.X, P(prav.Y.X, prav.X.X - 1));
    pair<P, P> ost = make_pair(P(prav.X.X, prav.X.X), prav.Y);
    return Add(RijesiPrazan(dol, stx, sty), RijesiDijag(ost, stx, sty));
  }

  if (prav.Y.X <= prav.X.Y)
    return RijesiPrazan(prav, stx, sty);

  pair<P, P> lijev = make_pair(prav.X, P(prav.X.Y - 1, prav.Y.Y));
  pair<P, P> ost = make_pair(P(prav.X.Y, prav.X.Y), prav.Y);
  return Add(RijesiPrazan(lijev, stx, sty), RijesiDijag(ost, stx, sty));
}

ll Rijesi(pair<P, P> prav)
{
  if (Invalid(prav))
    return 0;

  int stx = 1, sty = 1;

  if (prav.X.X < 0 && prav.Y.X < 0) {
    stx = -1;
    swap(prav.X.X, prav.Y.X);
    prav.X.X *= -1;
    prav.Y.X *= -1;
  }

  if (prav.X.Y < 0 && prav.Y.Y < 0) {
    sty = -1;
    swap(prav.X.Y, prav.Y.Y);
    prav.X.Y *= -1;
    prav.Y.Y *= -1;
  }

  return RijesiPrvi(prav, stx, sty);
}

int main()
{
  int n, brq;
  scanf("%d%d", &n, &brq);

  pair <P, P> pod[9];
  pod[0].X.Y = pod[1].X.Y = pod[2].X.Y = -n;
  pod[0].Y.Y = pod[1].Y.Y = pod[2].Y.Y = -2;

  pod[3].X.Y = pod[4].X.Y = pod[5].X.Y = -1;
  pod[3].Y.Y = pod[4].Y.Y = pod[5].Y.Y = 1;

  pod[6].X.Y = pod[7].X.Y = pod[8].X.Y = 2;
  pod[6].Y.Y = pod[7].Y.Y = pod[8].Y.Y = n;



  pod[0].X.X = pod[3].X.X = pod[6].X.X = -n;
  pod[0].Y.X = pod[3].Y.X = pod[6].Y.X = -2;

  pod[1].X.X = pod[4].X.X = pod[7].X.X = -1;
  pod[1].Y.X = pod[4].Y.X = pod[7].Y.X = 1;

  pod[2].X.X = pod[5].X.X = pod[8].X.X = 2;
  pod[2].Y.X = pod[5].Y.X = pod[8].Y.X = n;


  for (; brq--; ) {
    int x1, x2, y1, y2;
    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    pair<P, P> prav = make_pair(P(x1, y1), P(x2, y2));

    ll rje = 0;
    for (int i=0; i<9; i++) {
      pair<P, P> nov = Presjek(prav, pod[i]);
      if ((i & 1) || i == 4)
        rje = Add(rje, RijesiPrazan(nov, 1, 1));
      else
        rje = Add(rje, Rijesi(nov));
    }

    printf("%lld\n", rje);
  }

  return 0;
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
1000 100
-709 0 1000 123
-621 -1000 -102 -435
-602 -560 276 -356
-945 -590 0 -468
...
view   save

correct output
788057008
633127082
507903329
53165899
558016315
...
view   save

user output
788057008
633127082
507903329
53165899
558016315
...
view   save

Test 2

Group: 2

Verdict: ACCEPTED

input
1000000000 100
181053719 1000000000 181053719...
view   save

correct output
818946492
750635163
193830026
660632411
46072376
...
view   save

user output
818946492
750635163
193830026
660632411
46072376
...
view   save

Test 3

Group: 3

Verdict: ACCEPTED

input
100000 100
-88233 -87279 -49871 52277
-86645 -7997 48948 30702
-79916 -36210 -21257 -16821
0 57331 93163 100000
...
view   save

correct output
986592951
708386765
85336595
18263594
32233727
...
view   save

user output
986592951
708386765
85336595
18263594
32233727
...
view   save

Test 4

Group: 4

Verdict: ACCEPTED

input
1000000000 100
1 1 21134200 719983102
1 1 929463279 1000000000
1 1 68450838 1
1 1 84417340 297177199
...
view   save

correct output
695961158
957360176
137575768
522232140
58884045
...
view   save

user output
695961158
957360176
137575768
522232140
58884045
...
view   save

Test 5

Group: 5

Verdict: ACCEPTED

input
1000000000 100
-857489445 -1000000000 -432836...
view   save

correct output
902627632
581519884
819269364
857298983
278402948
...
view   save

user output
902627632
581519884
819269364
857298983
278402948
...
view   save