Show all threads Hide all threads Show all messages Hide all messages |
(C++ VS Go) What are the tests #2 and #6? | grinrag | 1178. Akbardin’s Roads | 29 Sep 2020 01:02 | 2 |
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 |
Hint | 👾_challenger128_👾 | 1178. Akbardin’s Roads | 26 Feb 2020 11:51 | 1 |
Hint 👾_challenger128_👾 26 Feb 2020 11:51 |
accpeted | Mikhail | 1178. Akbardin’s Roads | 4 Jun 2018 22:31 | 1 |
//#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 | Mahilewets | 1178. Akbardin’s Roads | 26 May 2017 11:46 | 1 |
If you got Median on the Plane AC you can get Akhbardin roads AC with the same code (with minimal changes). |
my AC (0.046s...) | dula | 1178. Akbardin’s Roads | 3 Jul 2015 02:15 | 3 |
#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 |
WA #2 | [ECUPL]David Yin | 1178. Akbardin’s Roads | 7 Jun 2015 16:50 | 1 |
WA #2 [ECUPL]David Yin 7 Jun 2015 16:50 Anyone know what is the test 2 ? |
Do not bother with shortest ways | alpha900i | 1178. Akbardin’s Roads | 11 Jun 2013 21:49 | 1 |
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. |
Who can help me?Write to this address:yuyuanming163@163.com | Tony | 1178. Akbardin’s Roads | 27 Nov 2012 12:44 | 9 |
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. |
Can anyone explain the problem? I can't understand it. | BYF | 1178. Akbardin’s Roads | 11 Nov 2012 18:29 | 3 |
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 |
Wrong statement? | Fyodor Menshikov | 1178. Akbardin’s Roads | 12 Jan 2009 01:42 | 2 |
"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 |
WA#6 | Mihran Hovsepyan {1 kurs of <RAU>} | 1178. Akbardin’s Roads | 8 Jul 2008 16:02 | 2 |
WA#6 Mihran Hovsepyan {1 kurs of <RAU>} 26 May 2008 00:35 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; } Re: WA#6 Mansurov Artur 8 Jul 2008 16:02 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; |
Problem 1178 "Akbardin’s Roads" statement updated (+) | Vladimir Yakovlev (USU) | 1178. Akbardin’s Roads | 28 Jun 2008 01:50 | 1 |
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:51 |
what is n is odd | tache | 1178. Akbardin’s Roads | 13 Mar 2006 09:18 | 2 |
if n is odd then how do write? |
Strange | XmasSoul | 1178. Akbardin’s Roads | 9 Jan 2006 15:51 | 1 |
O(n^2) sort is AC, too... |
can sample output be this? | young master | 1178. Akbardin’s Roads | 28 Jun 2004 18:48 | 2 |
Yes (-) Dmitry 'Diman_YES' Kovalioff 28 Jun 2004 18:48 |
my solution here | ural_Lai yilong | 1178. Akbardin’s Roads | 13 May 2003 18:18 | 2 |
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. |