I am learning Golang and rewriting my solutions from C++ to Golang, changes should no affect the result, but it started failing either on test #2 or test #6.

Could you, please, provide me those tests to understand what is the problem?

Thanks!

Edited by author 29.09.2020 01:07

Just a sort problem

//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("avx")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define re return
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sqrt(x) sqrt(abs(x))
#define mp make_pair
#define pi (3.14159265358979323846264338327950288419716939937510)
#define fo(i, n) for(int i = 0; i < n; ++i)
#define ro(i, n) for(int i = n - 1; i >= 0; --i)
#define unique(v) v.resize(unique(all(v)) - v.begin())

template <class T> T abs (T x) { re x > 0 ? x : -x; }
template <class T> T sqr (T x) { re x * x; }
template <class T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; }
template <class T> int sgn (T x) { re x > 0 ? 1 : (x < 0 ? -1 : 0); }

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
typedef double D;
typedef long double ld;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef unsigned long long ull;
typedef tree <pair<int, char>, null_type, less<pair<int, char>>, rb_tree_tag, tree_order_statistics_node_update> _tree;

int main() {
    int n;
    cin >> n;
    vector <pair<ii, int>> v(n);
    fo(i, n) {
        cin >> v[i].fi.fi >> v[i].fi.se;
        v[i].se = i + 1;
    }
    sort(all(v));
    for (int i = 0; i < n; i += 2) {
        cout << v[i].se << ' '<< v[i + 1].se << '\n';
    }
}

If you got Median on the Plane AC you can get Akhbardin roads AC with the same code (with minimal changes).

#include<stdio.h>
#include<deque>
#include<algorithm>
using namespace std;
class node{
    public:
    int x,y,num;
}dum;
bool func(node i,node j)
{
    if(i.y > j.y)
    return true;
    return false;
}
int main()
{
    deque<node> city;
    int n;    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d %d",&dum.x,&dum.y);
        dum.num = (i+1);
        city.push_back(dum);
    }
    if(n == 0)
    {printf("0");return 0;}
    sort(city.begin(),city.end(),func);
    for(int i=0;i<n;i+=2)
    {
        printf("%d %d\n",city[i].num,city[i+1].num);
    }
}

Anyone know what is the test 2 ?

Spent some time trying to create algorithm, that would make shortest possible set of roads. Then understood, that Akbardin will fight for shortness later; atm he bothered only with having roads without crossing. That why task became so much easier... Hope this would save someone's time.

If the towns ought to be all connected with each other, then why there's just N/2 roads? I think there should at least be N-1 roads.

"no two roads should intersect"

What about test
4
0 1
0 2
0 3
0 4
Is answer
1 4
2 3
valid? Roads do not intersect, but they have common points. I think that if roads cannot intersect (no way to make multilevel road junctions) then they also cannot have common segments.

Who can help me?
Why I got WA#6
This is my code
# include <iostream>
using namespace std;
int main ()
{
    int n,i,j,k;
    int x[10002],y[10002],h[10002];
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i];
        h[i]=i;
    }
    for(i=1;i<n;i++)
        for(j=i+1;j<=n;j++)
        {
            if((x[j]<x[i]) || (x[j]==x[i] && y[j]>y[i]))
            {
                k=x[i];x[i]=x[j];x[j]=k;
                k=y[i];y[i]=y[j];y[j]=k;
                k=h[i];h[i]=h[j];h[j]=k;
            }
        }
    for(i=1;i<=(n/2)+1;i+=2)
        cout<<h[i]<<" "<<h[i+1]<<endl;
    return 0;
}

Russian statement has been updated and now corresponds to English one. This line has been added:It corresponds to English
Edited by author 28.06.2008 01:51

if n is odd then how do write?

O(n^2) sort is AC, too...

1 2
3 4

var a:array[1..10000]of longint;
    b:array[1..10000]of integer;
    q,l,r,j,i,x,n:longint;
procedure Qsort(l,r:integer);
begin
     if l>=r then exit;
     j:=r;i:=l;x:=a[i];
     while not(i=j) do begin
           while (a[j]>x)and(j>i) do dec(j);
           if i<j then begin q:=a[i];a[i]:=a[j];a[j]:=q;
                             q:=b[i];b[i]:=b[j];b[j]:=q;inc(i);end;
           while (a[i]<x)and(j>i) do inc(i);
           if i<j then begin q:=a[j];a[j]:=a[i];a[i]:=q;
                             q:=b[i];b[i]:=b[j];b[j]:=q;j:=j-1;end;
           end;
     x:=a[i];
     if l<(i-1) then Qsort(l,i-1);
     if (i+1)<r then Qsort(i+1,r);
end;
begin
     read(n);
     for i:=1 to n do readln(a[i]);
     for i:=1 to n do b[i]:=i;
     Qsort(1,n);
     for i:=1 to n div 2 do writeln(b[2*i-1],' ',b[2*i]);
     readln;
end.