oj.uz

Submission #698658

# Submission time Handle Problem Language Result Execution time Memory
698658 2023-02-14T07:15:25 Z vjudge1 Circle selection (APIO18_circle_selection) C++17
0 / 100
 3000 ms 20816 KB 
#include "bits/stdc++.h"
#define ll long long
#define pb push_back
#define endl '\n'

using namespace std;
ll INF= 1e18+79;

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<ll,ll>a,pair<ll,ll>b)
{
  if(a.first!=b.first)
    return (a.first>b.first);
  return (a.second<b.second);
}

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

    ll n;
    cin>>n;
    vector<pair<ll,ll>>v(n),c(n);
    for(int i=0;i<n;i++)
    {
      ll x,y,r;
      cin>>x>>y>>r;
      c[i]={x,y};
      v[i]={r,i};
    }

    sort(v.begin(),v.end(),sorting);

    ll ans[n]={};
    for(int i=0;i<n;i++)
    {
      if(ans[v[i].second])continue;
      for(int j=0;j<n;j++)
      {
        if(ans[v[j].second])continue;

        if(dis(c[v[i].second],c[v[j].second])<=(v[i].first+v[j].first)*(v[i].first+v[j].first) )
          ans[v[j].second]=v[i].second;
      }
    }
    for(int i=0;i<n;i++)
      cout<<ans[i]+1<<' ';
    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
*/

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 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 Correct 133 ms 20808 KB Output is correct
2 Correct 219 ms 20788 KB Output is correct
3 Correct 136 ms 20544 KB Output is correct
4 Correct 138 ms 20816 KB Output is correct
5 Execution timed out 3041 ms 16612 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 3071 ms 6964 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3052 ms 19904 KB Time limit exceeded
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 1 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 1 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -