Submission #1312530

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312530		wjankowski	Power Plant (JOI20_power)	C++20	0 / 100	2 ms	2360 KiB

power

#include <bits/stdc++.h>
using namespace std;

#define pi pair<int,int>
#define ll long long
#define ld long double
constexpr int maxn = 1e5+2;

struct p
{
  int x,y;
  pi kw;
  int it;

  bool operator<(p o)
  {
    return kw < o.kw;
  }
}P[maxn];

ll dis(p a, p b)
{
  ll dx=a.x-b.x, dy=a.y-b.y;
  return dx*dx+dy*dy;
}

int n,col[maxn];
vector <int> con[maxn],ls[2];

bool dfs(int v)
{
  bool f=1;
  for(auto u : con[v])
  {
    if(col[u] == col[v]) return 0;
    if(col[u] == -1)
    {
      col[u]=1-col[v];
      f &= dfs(u);
      if(!f) return 0;
    }
  }
  return f;
}

bool dwudzielny()
{
  for(int i=0; i<n; i++) col[i]=-1;
  bool f=1;
  for(int i=0; i<n; i++)
  {
    if(col[i] == -1)
    {
      col[i]=0;
      f &= dfs(i);
    }
  }
  return f;
}

bool check(ll D)
{
  ld r = sqrtl((ld)D/2.0);
  for(int i=0; i<n; i++)
  {
    P[i].kw.first = floorl(P[i].x/r);
    P[i].kw.second = floorl(P[i].y/r);
    con[i].clear();
  }
  sort(P,P+n); int cnt=1;
  for(int i=0; i<n; i++)
  {
    if(i == 0 || P[i].kw != P[i-1].kw) cnt=1;
    else cnt++;

    if(cnt > 2) return 0;
  }

  for(int i=0; i<n; i++)
  {
    for(int x=P[i].kw.first-2; x<=P[i].kw.first+2; x++)
    {
      for(int y=P[i].kw.second-2; y<=P[i].kw.second+2; y++)
      {
        int st=lower_bound(P,P+n,(p){0,0,pi(x,y),0})-P;
        for(int j=st; j<n && P[j].kw == pi(x,y); j++)
          if(dis(P[i],P[j]) < D && i != j)
            con[P[i].it].push_back(P[j].it);
      }
    }
  }
  return dwudzielny();
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n;
	for(int i=0; i<n; i++)
	{
		cin >> P[i].x >> P[i].y;
		P[i].it=i;
	}
	ll l=1,r=2e18+1;
  while(l < r)
  {
    ll mid=(l+r+1)/2;
    if(check(mid)) l=mid;
    else r=mid-1;
  }
  cout << l << '\n';
  check(l);

  for(int i=0; i<n; i++)
    ls[col[i]].push_back(i+1);

  for(int c=0; c<=1; c++)
  {
    cout << (int)ls[c].size() << '\n';
    for(auto v : ls[c]) cout << v << ' ';
    cout << '\n';
  }
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 41
• Subtask 3: 0 / 53