Skip to content

Instantly share code, notes, and snippets.

@novaknole
Created December 20, 2020 11:06
Show Gist options
  • Save novaknole/ae5c80575904a2f75e2f369fde81de2e to your computer and use it in GitHub Desktop.
Save novaknole/ae5c80575904a2f75e2f369fde81de2e to your computer and use it in GitHub Desktop.
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
struct Point
{
Point(char tag, int x, int y)
:m_tag(tag)
,m_dist(long(x)*long(x) + long(y)*long(y))
{
}
friend bool operator<(Point a, Point b)
{
if(a.m_dist == b.m_dist)
{
return a.m_tag < b.m_tag;
}
return a.m_dist < b.m_dist;
}
char m_tag;
long m_dist;
};
int solution(string &s, vector<int> &x, vector<int> &y)
{
vector<Point> points;
int n = x.size();
points.reserve(n);
for(int i = 0;i<n;++i)
{
points.emplace_back(s[i],x[i],y[i]);
}
sort(points.begin(),points.end());
bool found[26] = {};
int total = 0;
found[points[0].m_tag] = true;
long current = points[0].m_dist;
int tentative = 0;
for(int i = 1;i<n;++i)
{
if(current == points[i].m_dist)
{
if(found[points[i].m_tag])
{
break;
}
found[points[i].m_tag] = true;
++tentative;
continue;
}
total += tentative;
if(found[points[i].m_tag])
{
return total;
}
tentative = 1;
found[points[i].m_tag - 'A'] = true;
current = points[i].m_dist;
}
return total;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment