oj.uz

Submission #254318

# Submission time Handle Problem Language Result Execution time Memory
254318 2020-07-29T20:42:04 Z shayan_p Circle selection (APIO18_circle_selection) C++14
23 / 100
 1741 ms 54788 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));
}

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1536 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Runtime error 5 ms 2944 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 183 ms 28268 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 2944 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1741 ms 47296 KB Output is correct
2 Correct 1157 ms 54124 KB Output is correct
3 Correct 495 ms 30184 KB Output is correct
4 Correct 1238 ms 54436 KB Output is correct
5 Correct 1210 ms 54788 KB Output is correct
6 Correct 292 ms 25196 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1536 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Runtime error 5 ms 2944 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1536 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Runtime error 5 ms 2944 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -