| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 282096 |
2020-08-24T02:38:28 Z |
NaimSS |
Park (BOI16_park) |
C++14 |
|
2500 ms |
53164 KB |
#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
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;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
651 ms |
53036 KB |
Output is correct |
| 2 |
Correct |
644 ms |
52908 KB |
Output is correct |
| 3 |
Correct |
674 ms |
53088 KB |
Output is correct |
| 4 |
Correct |
646 ms |
53164 KB |
Output is correct |
| 5 |
Correct |
643 ms |
52908 KB |
Output is correct |
| 6 |
Correct |
641 ms |
53036 KB |
Output is correct |
| 7 |
Correct |
619 ms |
52908 KB |
Output is correct |
| 8 |
Correct |
605 ms |
52908 KB |
Output is correct |
| 9 |
Correct |
2 ms |
3456 KB |
Output is correct |
| 10 |
Correct |
2 ms |
3456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2560 ms |
7152 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
651 ms |
53036 KB |
Output is correct |
| 2 |
Correct |
644 ms |
52908 KB |
Output is correct |
| 3 |
Correct |
674 ms |
53088 KB |
Output is correct |
| 4 |
Correct |
646 ms |
53164 KB |
Output is correct |
| 5 |
Correct |
643 ms |
52908 KB |
Output is correct |
| 6 |
Correct |
641 ms |
53036 KB |
Output is correct |
| 7 |
Correct |
619 ms |
52908 KB |
Output is correct |
| 8 |
Correct |
605 ms |
52908 KB |
Output is correct |
| 9 |
Correct |
2 ms |
3456 KB |
Output is correct |
| 10 |
Correct |
2 ms |
3456 KB |
Output is correct |
| 11 |
Execution timed out |
2560 ms |
7152 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
