Submission #254353

#	Time	Username	Problem	Language	Result	Execution time	Memory
254353		shayan_p	Circle selection (APIO18_circle_selection)	C++14	7 / 100	3091 ms	17728 KiB

circle_selection

// And you curse yourself for things you never done
 
#include<bits/stdc++.h>
 
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
 
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int maxn = 3e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;
 
pair<pll, ll> p[maxn];
int arr[maxn], ans[maxn];
 
pll operator - (pll a, pll b){
    return {a.F - b.F, a.S - b.S};
}
pll operator + (pll a, pll b){
    return {a.F + b.F, a.S + b.S};
}
ll operator ^ (pll a, pll b){
    return 1ll * a.F * b.F + 1ll * a.S * b.S;
}
bool ok(int i, int j){
    return 1ll * (p[j].S + p[i].S) * (p[j].S + p[i].S) >= ((p[i].F - p[j].F) ^ (p[i].F - p[j].F));
}

struct Hash{
    int operator() (const pii &p)const{
	return hash<ll>()( (ll(p.F) << 32) | ll(p.S) );
    }
};

const int Log = 0; //// kam nis? ////////////////

struct node{
    node *nxt[2][2];
    vector<int> vec;
    node(){
	nxt[0][0] = nxt[0][1] = nxt[1][0] = nxt[1][1] = 0;
    }
};node* rt;

void add(int msk1, int msk2, int id){
    node* nw = rt;
    for(int i = Log-1; i >= 0; i--){
	nw->vec.PB(id);
	if(nw->nxt[bit(msk1, i)][bit(msk2, i)] == 0)
	    nw->nxt[bit(msk1, i)][bit(msk2, i)] = new node();
	nw = nw->nxt[bit(msk1, i)][bit(msk2, i)];
    }
    nw->vec.PB(id);
}
node* fnd(int msk1, int msk2, int len){
    node* nw = rt;
    for(int i = Log-1; i >= Log-len; i--){
	if(nw->nxt[bit(msk1, i)][bit(msk2, i)] == 0)
	    return 0;
	nw = nw->nxt[bit(msk1, i)][bit(msk2, i)];
    }
    return nw;
}

int cnt[maxn];

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

    rt = new node();
	
    memset(ans, -1, sizeof ans);

    int n;    
    cin >> n;

    for(int i = 0; i < n; i++){
	cin >> p[i].F.F >> p[i].F.S >> p[i].S;
	p[i].F.F+= inf, p[i].F.S+= inf;
    }
    auto cmp = [](int i, int j){
		   return (p[i].S == p[j].S ? i > j : p[i].S < p[j].S);
	       };
    iota(arr, arr + n, 0);
    sort(arr, arr + n, cmp);
    
    for(int i = 0; i < n; i++){
	add(p[i].F.F, p[i].F.S, i);
    }
    
    int len = 0;
    
    for(int I = n-1; I >= 0; I--){
	int i = arr[I];
	while(Log > len && (1<<(Log-len-1)) >= p[i].S)
	    len++;
	if(ans[i] == -1){
	    ans[i] = i;
	    int x = p[i].F.F, y = p[i].F.S, df = 1<<(Log-len);
	    for(int X = x - 2 * df; X <= x + 2 * df; X+= df){
		for(int Y = y - 2 * df; Y <= y + 2 * df; Y+= df){
		    node* nw = fnd(X , Y, len);
		    if(nw){
			vector<int> vec;
			for(int id : nw->vec){
			    if(ans[id] == -1 && ok(id, i))
				ans[id] = i;
			    if(ans[id] == -1)
				vec.PB(id);//, assert(++cnt[id] <= 10);
			}
			nw->vec = vec;
		    }
		}
	    }
	}
    }
    for(int i = 0; i < n; i++){
	cout << ans[i] + 1 << " ";
    }
    return cout << endl, 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13