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 Ok, looks like in my case the format of input data in tests #2 and #6 is differ from the one in the example. Accepted Go code is: package main import ( "fmt" "sort" ) type city struct { n, x, y int } func main() { var n int fmt.Scan(&n) m := make([]city, n) for i := 0; i < n; i++ { m[i].n = i + 1 fmt.Scan(&m[i].x, &m[i].y) } sort.Slice(m, func(i, j int) bool { if m[i].x < m[j].x { return true } return false }) for i := 0; i < n; i += 2 { fmt.Println(m[i].n, m[i+1].n) } } time: 0.14 memory: 2 044 КB Edited by author 29.09.2020 01:10 //#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); } } your code is wrong http://ideone.com/2mv3As it prints 3 4 1 2 instead of 1 3 2 4 for the test from description of the problem perhaps it gaves AC so your code is right, tests are wrong or problem description is not completed 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. follow is my program: var a:array[1..10000]of longint; z:array[1..10000]of integer; i,j,k,n:longint; begin fillchar(a,sizeof(a),0); fillchar(z,sizeof(z),0); read(n); for i:=1 to n do begin read(a[i],j);z[i]:=i;end; for i:=1 to n-1 do for j:=i+1 to n do if a[z[i]]>a[z[j]] then begin k:=z[i]; z[i]:=z[j]; z[j]:=k; end; i:=0; while i<n do begin writeln(z[i+1],' ',z[i+2]); inc(i,2); end; end. Try this: 4 1 1 1 3 1 2 1 4 Your program says 1 2 3 4 but those roads intersect. My first solution was wrong also, but I sort towns by polar angle and I can choose center randomly. TO JUDGES: Can you add few tests that catch solutions, which sort towns only by X or by Y? I think this is incorrect test. Because, No three towns lay on one line. Your solution looks so strange! Can you tell me why it works? Oh, you needn't explain it to me any more. I have understood it! Ha! Very funny! I got it! Oh, yeah!!!!!!!!!!!!! bravoooo!!! Your idea is very good. 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. oooooooooooh,I know. I've been a fool for so many times. I can't understand this problem.Plz "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. No three towns lay on one line. This test is incorrect 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; } problem in output if you use for(...;i+=2) you have to use for(...;i<=n;...) //like this for(i=1;i<=n;i+=2) cout<<h[i]<<" "<<h[i+1]<<endl; Russian statement has been updated and now corresponds to English one. This line has been added: Никакие три города не лежат на одной прямой. It corresponds to English No three towns lay on one line. Edited by author 28.06.2008 01:51if n is odd then how do write? O(n^2) sort is AC, too... 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. |
|