제출 #988974

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
988974		vjudge1	Hexagonal Territory (APIO21_hexagon)	C++17	11 / 100	399 ms	10332 KiB

hexagon

#include "hexagon.h"
#include <bits/stdc++.h>
#include <vector>
#define debu(x) (cerr << #x  << " = "<< x << "\n")
#define moddy 1000000007
#define ff first
#define pii pair<int,int>
#define piii pair<pii,int>
#define pb push_back
#define ss second
#define ll long long 
using namespace std;

/*bool bins(vector<bool> &chosen, pii cha)
{
	//cout << "inbins\n";
	if (cha.ff > 4000 || cha.ff < 0)return false;
	if (cha.ss > 8000 || cha.ss < 0) return false;
	return (chosen[cha.ff*10000+cha.ss]);
}*/


int draw_territory(int N, int A, int B, std::vector<int> D, std::vector<int> L)
{
  //cout << "in terr\n";
  #define int long long
  vector<pii>dir = {{0,2},{1,1},{1,-1},{0,-2},{-1,-1},{-1,1}};
  
  pii currat={2000,4000};
  vector<bool>chosen(40008001,1);
  chosen[20004000] = false;
  //cout << "ok";
  int path = 0;
  for (int a=0;a<N;a++)
  {
	  for (int b = 0; b<L[a];b++)
	  {
		  currat.ff += dir[D[a] - 1].ff;
		  currat.ss += dir[D[a] - 1].ss;
		  //cout << currat.ff*10000+currat.ss << "\n";
		  chosen[currat.ff*10000+currat.ss] = false;
		  path++;
	  }
  }
  //cout << path << "pathos\n";
  //cout << "can";
  queue<pii>tbc;
  vector<vector<bool>>grid(4001,vector<bool>(8001,1));
  tbc.push({4000,8002});
  //grid[2000][4000] = false;
  
  while(!tbc.empty())
  {
	  pii current = tbc.front();
	  //cout << current.ff << " " << current.ss << "\n";
	  tbc.pop();
	  
	  for (pii xx : dir)
	  {
		  if ((current.ff + xx.ff) >= 0 && (current.ff + xx.ff) <=4000 && (current.ss + xx.ss) >= 0 && (current.ss + xx.ss) <= 8000 && (chosen[(current.ff + xx.ff)*10000 + current.ss + xx.ss])&&(grid[current.ff + xx.ff][current.ss + xx.ss]))
		  {
			  tbc.push(make_pair(current.ff + xx.ff, current.ss + xx.ss));
			  grid[current.ff+ xx.ff][current.ss+ xx.ss] = false;
		  }
		  else continue;
	  }
  }
  int ans = 0;
  //cout << "exited out";
  
  //cout << "the ones we accepted:\n";
  int cour=0;
  map<int,int> xcom;
  queue<piii>tbf;
  tbf.push({{2000,4000},0});
  grid[2000][4000] = false;
  while (!tbf.empty())
  {
	  piii current = tbf.front();
	  //cout << current.ff.ff << " " << current.ff.ss << " : " << current.ss << "\n";
	  tbf.pop();
	  cour++;
	  ans += A;
	  ans%= moddy;
	  ans += current.ss * B;
	  ans %= moddy;
	  xcom[current.ss]+=1;
	  
	  for (pii xx : dir)
	  {
		  if ((current.ff.ff + xx.ff) >= 0 && (current.ff.ff + xx.ff) <=4000 && (current.ff.ss + xx.ss) >= 0 && (current.ff.ss + xx.ss) <= 8000 && (grid[current.ff.ff + xx.ff][current.ff.ss + xx.ss]))
		  {
			  tbf.push({make_pair(current.ff.ff + xx.ff, current.ff.ss + xx.ss),current.ss+1});
			  grid[current.ff.ff+ xx.ff][current.ff.ss+ xx.ss] = false;
		  }
		  else continue;
	  }
  }
  /*cout << "caroot:\n";
  for (auto x: xcom)
  {
	  cout << x.ff << " : " << x.ss << "\n";
  }
  cout << "kore " << cour << "\n";
  cout << ans << " ";*/
  #undef int 
  ans = ans%moddy;
  return ans;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 11 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 15
• Subtask 6: 0 / 19
• Subtask 7: 0 / 18
• Subtask 8: 0 / 16