oj.uz

Submission #533696

# Submission time Handle Problem Language Result Execution time Memory
533696 2022-03-06T23:52:36 Z DanerZein Hexagonal Territory (APIO21_hexagon) C++14
11 / 100
 1560 ms 1048576 KB 
#include "hexagon.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
const ll mod=1e9+7;
const int MAX_N=8e3;
int X[8]={0,-2,-1,1,2,1,-1};
int Y[8]={0,0,1,1,0,-1,-1};
ll he[MAX_N+10][MAX_N+10];
int vis[MAX_N+10][MAX_N+10];
ll pot(ll b,ll e){
  if(e==1) return b;
  ll aux=pot(b,e/2);
  aux*=aux; aux%=mod;
  if(e%2!=0) aux=(aux*b)%mod;
  return aux;
}
void flod(int x,int y){
  vis[x][y]=2;
  queue<ii> q;
  q.push(ii(x,y));
  while(!q.empty()){
    int x=q.front().first;
    int y=q.front().second;
    q.pop(); 
    for(int i=1;i<=6;i++){
      int xk=x+X[i];
      int yk=y+Y[i];
      if(xk>=0 && yk>=0 && xk<=MAX_N && yk<=MAX_N && !vis[xk][yk]){
	vis[xk][yk]=2;
	q.push(ii(xk,yk));
      }
    }
  }
}
void height(int x,int y){
  for(int i=0;i<=MAX_N;i++) for(int j=0;j<=MAX_N;j++) he[i][j]=1e9;
  he[x][y]=0;
  queue<ii> q;
  q.push(ii(x,y));
  while(!q.empty()){
    int xi=q.front().first;
    int yi=q.front().second;
    q.pop();
    for(int i=1;i<=6;i++){
      int xk=xi+X[i];
      int yk=yi+Y[i];
      if(xk>=0 && yk>=0 && xk<=MAX_N && yk<=MAX_N && vis[xk][yk]<=1){
	if(he[xk][yk]>he[xi][yi]+1){
	  he[xk][yk]=he[xi][yi]+1;
	  q.push(ii(xk,yk));
	}
      }
    }
  }
}
int draw_territory(int N, int A, int B,
                   std::vector<int> D, std::vector<int> L) {
  memset(he,-1,sizeof he);
  memset(vis,0,sizeof vis);
  ll ans=0;
  int x=4e3,y=4e3;
  vis[x][y]=1;
  for(int i=0;i<N;i++){
    for(int j=0;j<L[i];j++){
      x+=X[D[i]];
      y+=Y[D[i]];
      vis[x][y]=1;
    }
  }
  for(int i=1;i<=6;i++){
    x=4e3; y=4e3;
    while(x>=0 && y>=0 && x<=MAX_N && y<=MAX_N){
      x+=X[i];
      y+=Y[i];
    }
    x-=X[i];
    y-=Y[i];
    if(!vis[x][y]){
      flod(x,y);
      break;
    }
  }
  x=4e3; y=4e3;
  height(x,y);
  for(int i=0;i<=MAX_N;i++){
    for(int j=0;j<=MAX_N;j++){
      if(he[i][j]!=1e9){
	ans+=A; ans%=mod;
	ans+=B*he[i][j]; ans%=mod;
      }
    }
  }
  return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 818 ms 1048576 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 750 ms 1048576 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1361 ms 753820 KB Output is correct
2 Correct 1360 ms 753812 KB Output is correct
3 Correct 1348 ms 753768 KB Output is correct
4 Correct 1443 ms 753832 KB Output is correct
5 Correct 1397 ms 753692 KB Output is correct
6 Correct 1373 ms 753840 KB Output is correct
7 Correct 1382 ms 753872 KB Output is correct
8 Correct 1461 ms 753732 KB Output is correct
9 Correct 1350 ms 753864 KB Output is correct
10 Correct 1368 ms 753772 KB Output is correct
11 Correct 1345 ms 753764 KB Output is correct
12 Correct 1372 ms 753728 KB Output is correct
13 Correct 1389 ms 753664 KB Output is correct
14 Correct 1385 ms 753800 KB Output is correct
15 Correct 1376 ms 753892 KB Output is correct
16 Correct 1460 ms 753804 KB Output is correct
17 Correct 1409 ms 753732 KB Output is correct
18 Correct 1365 ms 753752 KB Output is correct
19 Correct 1358 ms 753864 KB Output is correct
20 Correct 1373 ms 753804 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 770 ms 1048576 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 737 ms 1048576 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1415 ms 753744 KB Output is correct
2 Correct 1369 ms 753820 KB Output is correct
3 Correct 1560 ms 753776 KB Output is correct
4 Correct 1356 ms 753880 KB Output is correct
5 Correct 1435 ms 753772 KB Output is correct
6 Correct 1389 ms 753728 KB Output is correct
7 Correct 1440 ms 753796 KB Output is correct
8 Correct 1382 ms 753656 KB Output is correct
9 Correct 1439 ms 753784 KB Output is correct
10 Correct 1364 ms 753808 KB Output is correct
11 Correct 1507 ms 753608 KB Output is correct
12 Correct 1436 ms 753708 KB Output is correct
13 Correct 1370 ms 754104 KB Output is correct
14 Correct 1409 ms 753824 KB Output is correct
15 Correct 1416 ms 753848 KB Output is correct
16 Correct 1449 ms 753772 KB Output is correct
17 Correct 1360 ms 753784 KB Output is correct
18 Runtime error 752 ms 1048576 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -

Subtask #7
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 759 ms 1048576 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1405 ms 753848 KB Output is correct
2 Runtime error 752 ms 1048576 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -