Submission #282096

#	Time	Username	Problem	Language	Result	Execution time	Memory
282096		NaimSS	Park (BOI16_park)	C++14	27 / 100	2560 ms	53164 KiB

park

#include <bits/stdc++.h>
#define ld long double
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define ms(v,x) memset(v,x,sizeof(v))
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define td(v) v.begin(),v.end()
#define sz(v) (int)v.size()
#define int long long
using namespace std;
typedef vector<int> vi;
#define y1 abacaba
#define left sefude
#define db(x) cerr << #x <<" == "<<x << endl;
#define db2(x,y) cerr<<#x <<" == "<<x<<", "<<#y<<" == "<<y<<endl;
typedef long long ll;
typedef pair<int,int> pii;
inline ll mod(ll n, ll m ){ ll ret = n%m; if(ret < 0) ret += m; return ret; }
ll gcd(ll a, ll b){return (b == 0LL ? a : gcd(b, a%b));}
ll exp(ll a,ll b,ll m){
    if(b==0LL) return 1LL;
    if(b==1LL) return mod(a,m);
    ll k = mod(exp(a,b/2,m),m);
    if(b&1LL){
        return mod(a*mod(k*k,m),m);
    }
    else return mod(k*k,m);
}


struct query{
  int r,e,id;
  query(){}
  query(int r,int e,int id):r(r),e(e),id(id){}
};
const int N = 2020;
int pai[N],Sz[N];

int f(int x){
  return pai[x] = (pai[x]==x?x:f(pai[x]));
}
void join(int a,int b){
  a=f(a),b=f(b);
  if(Sz[a] > Sz[b])swap(a,b);
  Sz[b]+=Sz[a];
  pai[a]=b;
}

ll sq(ll x){return x*x;}

pii Par[5];
string res[100100];
int x[N],y[N],r[N];
int32_t main(){
  fastio;
  int n,m;
  cin >> n >> m;
  int w,h;
  cin >> w >> h;
  Par[1] = pii(0,1);
  Par[2] = pii(w,0);
  Par[3] = pii(h,1);
  Par[4] = pii(0,0);
  for(int i=1;i<=n;i++){
    cin >> x[i] >> y[i] >> r[i];
  }
  for(int i=1;i<=n+4;i++)pai[i] = i,Sz[i] = 1;

  vector<query> qry;
  for(int i=0;i<m;i++){
    int r,e;
    cin >> r >> e;
   qry.pb(query(r,e,i));
  }

  sort(all(qry),[&](query a,query b){
    return a.r < b.r;
  });
  
  vector<query> circ,parede;
  
  for(int i=1;i<=n;i++){

    for(int j=i + 1;j<=n;j++){
      ll L = 0 , R = 1e9;
      ll ans = 0;
      while(L<=R){
        ll mid = (L+R)/2;
        if(sq(r[i] + r[j] + mid*2)>=sq(x[i] - x[j]) + sq(y[i]-y[j])){
          ans = mid;
          R = mid-1;
        }else L = mid + 1;

      }
      if(sq(r[i] + r[j] + 2*ans) == sq(x[i] -x[j]) + sq(y[i] - y[j])){
        ans++;
      }
      // please dont TL..
      circ.pb(query(ans,i,j));
    }
    
    for(int lado=1;lado<=4;lado++){
      if(Par[lado].ss == 0){
        // X
        int falta = (abs(Par[lado].ff - x[i])-r[i] + 1)/2;
        if(abs(Par[lado].ff - x[i]) == r[i] + 2 * falta)falta++;
        parede.pb(query(falta,i,n + lado));
      }else{
        // Y
        int falta = (abs(Par[lado].ff - y[i]) - r[i]+1)/2;

        if(abs(Par[lado].ff - y[i]) == r[i] + 2 * falta)falta++;
        parede.pb(query(falta,i,n + lado));
      }
    }

  }
  sort(all(circ),[&](query a,query b){
    return a.r < b.r;
  });
  sort(all(parede),[&](query a,query b){
    return a.r < b.r;
  });

  int it = 0;
  int itP=0;
  
  for(auto pessoa : qry){
    for(int i=1;i<=n;i++){
      for(int j=i+1;j<=n;j++){
        if(sq(r[i] + r[j] + 2*pessoa.r) > sq(x[i] - x[j]) + sq(y[i] - y[j]))join(i,j);
      }
      if(x[i]-r[i]-pessoa.r*2<0)join(i,n+4);
      if(y[i]-r[i]-pessoa.r*2<0)join(i,n+1);
      if(x[i]+r[i]+pessoa.r*2>w)join(i,n+2);
      if(y[i]+r[i]+pessoa.r*2>h)join(i,n+3);
    }
    /*
    while(it < sz(circ) and circ[it].r <= pessoa.r){
      join(circ[it].e,circ[it].id);
      it++;
    }
    while(itP < sz(parede) and parede[itP].r<=pessoa.r){
      join(parede[itP].e,parede[itP].id);
      itP++;
    }
    */
    int e = pessoa.e;
    string good = "";
    for(int c=1;c<=4;c++){
      if(c==e){
        good+=char('0' + c);
        continue;
      }
      // check if vertical blocks:
      int op1 = (min(e,c)==1 and max(e,c)==4);
      int op2 = (min(e,c)==2 and max(e,c)==3);
      if(!op1 and !op2){

        if(f(n + 1) == f(n + 3))continue;
      }

      op1 = (min(e,c)==1 and max(e,c)==2);
      op2 = (min(e,c)==3 and max(e,c)==4);

      // check if horizontal blocks:
      if(!op1 and !op2){
        if(f(n+2)==f(n+4))continue;
      }

      //cout << c<<" "<<f(n+3)<<" "<<f(n + (c+3)%4) << endl;
      int prv = n + (c == 1 ? 4 : c - 1);
      if(f(n + c) == f(prv))continue;
      good+=char('0' + c);
    }
    sort(all(good));
    res[pessoa.id] = good;
  }
  for(int i=0;i<m;i++)cout << res[i] << endl;

  // math -> gcd it all
  // Did u check N=1? Did you switch N,M?
}

Compilation message (stderr)

park.cpp: In function 'int32_t main()':
park.cpp:133:7: warning: unused variable 'it' [-Wunused-variable]
  133 |   int it = 0;
      |       ^~
park.cpp:134:7: warning: unused variable 'itP' [-Wunused-variable]
  134 |   int itP=0;
      |       ^~~

• Subtask 1: 27 / 27
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42