Submission #254318

#	Time	Username	Problem	Language	Result	Execution time	Memory
254318		shayan_p	Circle selection (APIO18_circle_selection)	C++14	23 / 100	1741 ms	54788 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));
}

map<pii, vector<int> > mp, mp2;
int Log = 31;
int n;

int cnt[maxn];

vector<int> vvv[2][2];

void reSize(){
    --Log;    
    mp2.clear();
    for(auto &it : mp){
	vvv[0][0].clear();
	vvv[0][1].clear();
	vvv[1][0].clear();
	vvv[1][1].clear();
	for(auto x : it.S){
	    if(ans[x] == -1)
		vvv[bit(p[x].F.F, Log)][bit(p[x].F.S, Log)].PB(x);
	}
	if(!vvv[0][0].empty())
	    mp2[{2 * it.F.F, 2 * it.F.S}] = vvv[0][0];
	if(!vvv[0][1].empty())
	    mp2[{2 * it.F.F, 2 * it.F.S + 1}] = vvv[0][1];
	if(!vvv[1][0].empty())
	    mp2[{2 * it.F.F + 1, 2 * it.F.S}] = vvv[1][0];
	if(!vvv[1][1].empty())
	    mp2[{2 * it.F.F + 1, 2 * it.F.S + 1}] = vvv[1][1];	
    }
    mp = mp2;
}

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

    memset(ans, -1, sizeof ans);
    
    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);

    vector<int> chert;
    for(int i = 0; i < n; i++)
	chert.PB(i);
    mp[{0,0}] = chert;


    while(Log > 0 && (1<<(Log-1)) >= p[0].S)
	Log--;
    for(int i = 0; i < n; i++)
	mp[{p[i].F.F >> Log, p[i].F.S >> Log}].PB(i);
    
    for(int I = n-1; I >= 0; I--){
	int i = arr[I];
	while(Log > 0 && (1<<(Log-1)) >= p[i].S)
	    assert(0), reSize();
	if(ans[i] == -1){
	    ans[i] = i;
	    int x = p[i].F.F >> Log, y = p[i].F.S >> Log;
	    for(int X = x-2; X <= x+2; X++){
		for(int Y = y-2; Y <= y+2; Y++){
		    if(mp.count({X, Y})){
			vector<int> vec;
			for(int id : mp[{X, Y}]){
			    if(ans[id] == -1 && ok(id, i))
				ans[id] = i;
			    if(ans[id] == -1)
				vec.PB(id);//, assert(++cnt[id] <= 10);
			}
			if(!vec.empty())
			    mp[{X, Y}] = vec;
		    }
		}
	    }
	}
    }
    for(int i = 0; i < n; i++){
	cout << ans[i] + 1 << " ";
    }
    return cout << endl, 0;
}

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