Submission #1036562

---

Source Code Expand

#include<bits/stdc++.h>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second

using namespace std;


#ifdef DEB
#define dump(x)  cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
#define dumpR(x) cerr<<"\x1b[31m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpY(x) cerr<<"\x1b[33m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpG(x) cerr<<"\x1b[32m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
#else
#define dump(x) ;
#define dumpR(x) ;
#define dumpY(x) ;
#define dumpG(x) ;
#define prl ;
template<class T> void debug(T a,T b){ ;}
#endif

template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; }
template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; }

typedef long long int lint;
typedef pair<int,int> pi;

namespace std{
  template<class S,class T>
  ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.fr<<','<<a.sc<<')';
    return out;
  }
}

//const int INF=5e8;
void ng(){
  puts("-1");
  exit(0);
}
typedef vector<int> vi;
typedef vector<pi> vp;

const int M=5e8;

void rot(vp& res){
  for(auto& p:res){
    pi nxt=mp(-p.sc,p.fr);
    p=nxt;
  }
}

vp solve(vi ar){
  int n=ar.size();
  if(n==4){
    vp res={{0,0},{1,0},{1,1},{0,1}};
    return res;
  }

  bool suc=false;
  vi pvar=ar;
  vector<int> pv;
  REP(i,n) if(ar[i]==1 && ar[(i+1)%n]==1 && ar[(i+2)%n]==3){
    REP(j,i) pv.pb(ar[j+1]);

    rotate(ar.begin(),ar.begin()+i,ar.end());
    suc=true;
    break;
  }
  assert(suc);
  vi chil=ar;
  ar.erase(ar.begin()+1);
  ar.erase(ar.begin()+1);

  vp res=solve(ar);
  prl;
  debug(ALL(ar));
  debug(ALL(res));
  int y=res[0].sc,x=res[0].fr;

  for(auto& p:res){
    if(p.sc<y) --p.sc;
    if(p.fr>x) ++p.fr;
  }

  res[0].sc--;
  res.insert(res.begin()+1,res[0]);
  res[1].fr++;
  res.insert(res.begin()+2,res[1]);
  res[2].sc++;
    debug(ALL(res));

  if(!pv.empty()){
    rotate(res.begin(),res.begin()+res.size()-pv.size(),res.end());
    int sign=0;
    for(auto e:pv){
      if(e==3) --sign;
      else ++sign;
    }
    sign=(sign%4+4)%4;
    REP(_,sign) rot(res);
  }
  debug(ALL(pvar));
  debug(ALL(res));
  return res;
}
int main(){
  int n;
  cin>>n;
  int one=0,thr=0;
  vi ar(n);
  REP(i,n){
    cin>>ar[i];
    if(ar[i]==90) ++one;
    else ++thr;
    ar[i]/=90;
  }
  if(n&1) ng();
  if(one-thr!=4) ng();

  vp res=solve(ar);

  for(auto p:res){
    printf("%d %d\n",p.fr+M,p.sc+M);
  }






  return 0;
}

Submission Info

Judge Result