oj.uz

Submission #254347

# Submission time Handle Problem Language Result Execution time Memory
254347 2020-07-29T21:23:42 Z shayan_p Circle selection (APIO18_circle_selection) C++14
0 / 100
 3000 ms 1043952 KB 
// 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 = 28; //// 

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);
			}
			if(!vec.empty())
			    nw->vec = vec;
		    }
		}
	    }
	}
    }
    for(int i = 0; i < n; i++){
	cout << ans[i] + 1 << " ";
    }
    return cout << endl, 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3083 ms 1536 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1257 ms 691464 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 3072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1371 ms 580688 KB Output is correct
2 Correct 1487 ms 556824 KB Output is correct
3 Runtime error 1697 ms 1043952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3083 ms 1536 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3083 ms 1536 KB Time limit exceeded
2 Halted 0 ms 0 KB -