oj.uz

Submission #698746

# Submission time Handle Problem Language Result Execution time Memory
698746 2023-02-14T09:14:23 Z vjudge1 Circle selection (APIO18_circle_selection) C++17
0 / 100
 220 ms 25184 KB 
#include "bits/stdc++.h"
#define ll long long
#define pb push_back
#define endl '\n'
#define fi first
#define sec second

using namespace std;
ll dis(pair<ll,ll>p1,pair<ll,ll>p2)
{
  ll a=(p1.first-p2.first) , b=(p1.second-p2.second);
  return (a*a)+(b*b);
}
bool sorting (pair<pair<ll,ll>,pair<ll,ll>>a,pair<pair<ll,ll>,pair<ll,ll>>b)
{
  if(a.fi.fi!=b.fi.fi)
    return (a.fi.fi>b.fi.fi);
  return (a.sec.sec<b.sec.sec);
}

signed main () {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    ll n;
    cin>>n;
    vector<pair<pair<ll,ll>,pair<ll,ll>>>v,c;

    for(int i=0;i<n;i++)
    {
      ll x,y,r;
      cin>>x>>y>>r;
      c.pb({{x-r,x+r},{r,i}});
      v.pb({{r,i},{x-r,x+r}});
    }
    sort(v.begin(),v.end(),sorting);
    sort(c.begin(),c.end());

    ll ans[n]={};
    for(int i=0;i<n;i++)
    {
      if(ans[v[i].fi.sec])continue;
      swap(v[i].sec,v[i].fi);
      auto u=lower_bound(c.begin(),c.end(),v[i]);
      for(ll j=u-c.begin();j<n;j++)
      {
        if(v[i].fi.sec<c[j].fi.fi)break;
        if(ans[c[j].sec.sec])continue;
        ans[c[j].sec.sec]=v[i].sec.sec+1;
      }
    }
    for(int i=0;i<n;i++)
      cout<<ans[i]<<' ';
    return 0;
}
/*
11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1

4
0 0 4
1 0 1
2 0 3
7 0 1



*/

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 188 ms 25184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 220 ms 25152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -