Submission #703008

#TimeUsernameProblemLanguageResultExecution timeMemory
703008NemanjaSo2005Pinball (JOI14_pinball)C++14
0 / 100
1072 ms1952 KiB
#include<bits/stdc++.h> #define ll long long using namespace std; /// N<=300 /// M<=2000 const string test="01"; ll N,M,L,degree[505],niz[505],pozicija[505],koji[505]; vector<int> graf[505]; struct cord{ int x,y,id; } tacke[505]; bool pox(cord x,cord y){ return x.x<y.x; } struct grana{ int a,b; } grane[2005]; bool podeg(int a,int b){ return degree[a]>degree[b]; } vector<int> V; void msbacaj(int L,int R){ if(R<L) return; int mid=(L+R)/2; V.push_back(mid); msbacaj(L,mid-1); msbacaj(mid+1,R); return; } int znak(int a){ if(a>0) return 1; if(a==0) return 0; return -1; } int strana(cord a,cord b,cord c){ return (c.y-a.y)*(b.x-a.x)-(c.x-a.x)*(b.x-a.x); } bool seku(cord a1,cord b1,cord a2,cord b2){ if(strana(a1,b1,a2)*strana(a1,b1,b2)>0) return false; if(strana(a2,b2,a1)*strana(a2,b2,b1)>0) return false; return true; } int prebroj(){ int ret=0; for(int i=1;i<=M;i++){ for(int j=i+1;j<=M;j++){ ret+=seku(tacke[pozicija[grane[i].a]],tacke[pozicija[grane[i].b]],tacke[pozicija[grane[j].a]],tacke[pozicija[grane[j].b]]); } } return ret; } void zameni(int a,int b){ if(koji[a]==0) pozicija[koji[b]]=a; else if(koji[b]==0) pozicija[koji[b]]=a; else swap(pozicija[koji[a]],pozicija[koji[b]]); swap(koji[a],koji[b]); } struct slog{ int koji,gde; }pp; queue<slog> Q; queue<int> K; int prosli[505],stavio[505]; int pvred,svred; void stavi(){ pvred++; int tren,tpoz; pp.koji=niz[1]; pp.gde=L/2; Q.push(pp); while(Q.size()){ tren=Q.front().koji; tpoz=Q.front().gde; Q.pop(); if(prosli[tren]==pvred) continue; prosli[tren]=pvred; while(K.size()) K.pop(); if(pozicija[tren]==0){ pozicija[tren]=tpoz; koji[tpoz]=tren; } svred++; int ml=1e9,vl=0,md=1e9,vd=0; for(int i=1;i<=L;i++){ int gde=tpoz-i; if(gde>=1) if(koji[gde]==0 and tacke[gde].y>vl or tacke[gde].y<ml){ vl=max(vl,tacke[gde].y); ml=min(ml,tacke[gde].y); K.push(gde); stavio[gde]=svred; } gde=tpoz+i; if(gde>=1) if(koji[gde]==0 and tacke[gde].y>vd or tacke[gde].y<md){ vd=max(vd,tacke[gde].y); md=min(md,tacke[gde].y); K.push(gde); stavio[gde]=svred; } } for(int i=1;i<=L;i++){ int gde=tpoz-i; if(gde>=1) if(koji[gde]==0 and stavio[gde]<svred){ K.push(gde); stavio[gde]=svred; } gde=tpoz+i; if(gde<=L) if(koji[gde]==0 and stavio[gde]<svred){ K.push(gde); stavio[gde]=svred; } } for(int i=0;i<graf[tren].size();i++){ if(koji[graf[tren][i]]!=0) continue; pp.gde=K.front(); pp.koji=graf[tren][i]; Q.push(pp); K.pop(); } } return; } ofstream ouf; void output(){ ouf.open(test+".out"); for(int i=1;i<=N;i++) ouf<<tacke[pozicija[i]].id<<endl; ouf.close(); return; } mt19937_64 rng; int main(){ while(true){ int x1,x2,y11,y2; cin>>x1>>y11>>x2>>y2; cord a,b,c,d; a.x=x1; a.y=y11; b.x=x2; b.y=y2; cin>>x1>>y11>>x2>>y2; c.x=x1; c.y=y11; d.x=x2; d.y=y2; cout<<seku(a,b,c,d)<<endl; } rng.seed(time(NULL)); ios_base::sync_with_stdio(false); cin.tie(0); ifstream inf; inf.open(test+".txt"); //#define cin inf cin>>N>>M; for(int i=1;i<=M;i++){ cin>>grane[i].a>>grane[i].b; degree[grane[i].a]++; degree[grane[i].b]++; graf[grane[i].a].push_back(grane[i].b); graf[grane[i].b].push_back(grane[i].a); } cin>>L; for(int i=1;i<=L;i++){ cin>>tacke[i].x>>tacke[i].y; tacke[i].id=i; } for(int i=1;i<=N;i++){ cin>>pozicija[i]; koji[pozicija[i]]=i; } cout<<prebroj()<<endl; return 0; for(int i=1;i<=N;i++) sort(graf[i].begin(),graf[i].end(),podeg); for(int i=1;i<=N;i++) niz[i]=i; sort(niz+1,niz+1+N,podeg); msbacaj(1,L); sort(tacke+1,tacke+1+L,pox); for(int i=1;i<=N;i++){ pozicija[i]=V[i-1]; koji[V[i-1]]=i; } stavi(); int nov,gmax,res=prebroj(); gmax=res; int a,b; cout<<"SKOR JE "<<res<<endl; while(true){ a=1; b=2; bool bolji=false; for(int a=1;a<=L;a++) for(int b=a+1;b<=L;b++){ //cout<<a<<" "<<b<<endl; if(koji[a]==koji[b]) continue; zameni(a,b); nov=prebroj(); if(nov<res){ bolji=true; if(nov<gmax){ cout<<"SKOR JE SADA "<<nov<<endl; output(); gmax=nov; } res=nov; continue; } zameni(a,b); } if(bolji==false){ for(int i=1;i<=N;i++){ int x=rng()%L+1; while(koji[x]!=0) x=rng()%L+1; pozicija[i]=x; koji[x]=i; } res=prebroj(); } } return 0; }

Compilation message (stderr)

pinball.cpp: In function 'void stavi()':
pinball.cpp:97:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   97 |             if(koji[gde]==0 and tacke[gde].y>vl or tacke[gde].y<ml){
      |                ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
pinball.cpp:105:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  105 |             if(koji[gde]==0 and tacke[gde].y>vd or tacke[gde].y<md){
      |                ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
pinball.cpp:128:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |         for(int i=0;i<graf[tren].size();i++){
      |                     ~^~~~~~~~~~~~~~~~~~
pinball.cpp: In function 'int main()':
pinball.cpp:205:9: warning: variable 'a' set but not used [-Wunused-but-set-variable]
  205 |     int a,b;
      |         ^
pinball.cpp:205:11: warning: variable 'b' set but not used [-Wunused-but-set-variable]
  205 |     int a,b;
      |           ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...