Mendo Judge Discussion Board - Forums
Search
Recent Topics
Hottest Topics
Member Listing
Back to home page
Танцување
Forum Index
»
Други задачи
Author
Message
27/03/2013 17:25:24
Subject:
Танцување
bedzo
Joined: 18/01/2011 02:05:03
Messages: 234
Offline
#include<cctype> #include<cmath> #include<string> #include<list> #include<deque> #include<stack> #include<utility> #include<sstream> #include<bitset> #include<vector> #include<algorithm> #include<cstring> #include<map> #include<set> #include<queue> #include<set> #include<iostream> #include<stdio.h> using namespace std; #define mp make_pair #define pb push_back #define ms(x,y) memset((x),(y),sizeof((x))) #define all(c) c.begin(),c.end() #define rep(i,n) for(int i=0;i<(int)n;i++) #define per(i,n) for(int i=n;i>=0;i--) #define PER(i,a,n) for(int i=n;i>=a;i++) #define REP(i,a,n) for(i=a;i<n;i++) #define IMA(v,x) ((v).find(x) != (v).end()) #define sz size() #define uni(v) { \ sort(all(v)); \ (v).erase(unique((v).begin(), (v).end()), (v).end()); \ } #define PI 3.141592653589793 #define EPS 0.000001 typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII; typedef vector<int> VI; typedef vector<string> VS; int n,a[100005],b[100005]; bool vis[100005]; struct node { int a,b,d; }; bool operator <(const node &a,const node &b) { return a.d>b.d; } int main() { int i,j; scanf("%d",&n); priority_queue<node> q; rep(i,n) scanf("%d",&a[i]); rep(i,n) scanf("%d",&b[i]); REP(i,1,n) if(b[i]!=b[i-1]) q.push(node{i-1,i,abs(a[i]-a[i-1])}); VI ans; ms(vis,false); while(!q.empty()) { node tmp=q.top(); q.pop(); //cout<<tmp.a<<" "<<tmp.b<<endl; if(vis[tmp.a] && vis[tmp.b]) continue; if(vis[tmp.a]) { for(i=tmp.b+1;i<n;i++) if(!vis[i]) { if(b[i]!=b[tmp.b]) q.push(node{tmp.b,i,abs(a[tmp.b]-a[i])}); break; } for(i=tmp.b-1;i>=0;i--) if(!vis[i]) { if(b[i]!=b[tmp.b]) q.push(node{i,tmp.b,abs(a[tmp.b]-a[i])}); break; } } else if(vis[tmp.b]) { for(i=tmp.a-1;i>=0;i--) if(!vis[i]) { if(b[i]!=b[tmp.a]) q.push(node{i,tmp.a,abs(a[tmp.a]-a[i])}); break; } for(i=tmp.a+1;i<n;i++) if(!vis[i]) { if(b[i]!=b[tmp.a]) q.push(node{tmp.a,i,abs(a[tmp.a]-a[i])}); break; } } else // mozeme da go zememe parot { ans.pb(tmp.a+1); ans.pb(tmp.b+1); vis[tmp.a]=true; vis[tmp.b]=true; int l=tmp.a,r=tmp.b; for(i=tmp.b+1;i<n;i++) if(!vis[i]) {r=i;break;} for(i=tmp.a-1;i>=0;i--) if(!vis[i]) {l=i;break;} if(tmp.b!=r && tmp.a!=l) if(b[r]!=b[l]) q.push(node{l,r,abs(a[l]-a[r])}); } } printf("%d\n",ans.sz/2); for(i=0;i<ans.sz;i+=2) printf("%d %d\n",ans[i],ans[i+1]); return 0; }
Ми минува на помалите примери,(11/20) а неможам да го најдам багот. Дали има врска како по ред треба да излегуваат паровите да танцуваат?
03/04/2013 13:24:28
Subject:
Танцување
bedzo
Joined: 18/01/2011 02:05:03
Messages: 234
Offline
bool operator <(const node &a,const node &b) { return a.d>b.d; }
во
bool operator <(const node &a,const node &b) { if(a.d==b.d) return a.a>b.a; return a.d>b.d; }
Forum Index
»
Други задачи
Go to:
Select a forum
Добродојдовте!
Општа дискусија
Задачи од национални натпревари
Задачи од меѓународни натпревари
Други задачи
Регионални натпревари
Државни натпревари
Македонски Олимпијади
Други натпревари
Pascal
C/C++
Јава
Други јазици
Powered by
JForum 2.1.8
©
JForum Team