Submission #11140229

---

Source Code Expand

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> T gcd(T a, T b){return !b?a:gcd(b,a%b);}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 2666;
int n,a[N],s;
vector<Pii>solve(Vi a){
	if(SZ(a)==4)return {mp(0,0),mp(1,0),mp(1,1),mp(0,1)};
	int offset=0;
	while(!(a[0]==1&&a[1]==1&&a[2]==-1)){
		auto tmp=a.back();per(i,SZ(a)-1,1)a[i]=a[i-1];a[0]=tmp;offset++;
	}
	
	Vi b;rep(i,0,SZ(a)-1)if(i!=1&&i!=2)b.pb(a[i]);
	vector<Pii>ans=solve(b);
	while(!(ans[0].fi<ans[1].fi&&ans[0].se==ans[1].se)){
		for(auto &a:ans)a=mp(a.se,SZ(ans)-a.fi+1);
	}
	for(auto &a:ans)a=mp(2*a.fi,2*a.se);
	auto tmp=ans[1];
	ans.insert(ans.begin()+2,mp(tmp.fi,tmp.se+1));
	ans.insert(ans.begin()+2,mp(tmp.fi+1,tmp.se+1));
	ans[1].fi++;
//	ans.insert(ans.begin()+2,mp(tmp.fi+1,tmp.se));
	b.clear();Vi c;for(auto x:ans)b.pb(x.fi),c.pb(x.se);
	sort(ALL(b));sort(ALL(c));
	for(auto &x:ans)x=mp(lower_bound(ALL(b),x.fi)-b.begin()+1,lower_bound(ALL(c),x.se)-c.begin()+1);
	
	offset=SZ(a)-offset;
	while(offset--){
		auto tmp=ans.back();per(i,SZ(ans)-1,1)ans[i]=ans[i-1];ans[0]=tmp;
	}
	return ans;
}
int main() {
	read(n);rep(i,1,n)read(a[i]),a[i]=a[i]==90?1:-1,s+=a[i];
	if(s!=4){puts("-1");return 0;}
	Vi b;rep(i,1,n)b.pb(a[i]);
	vector<Pii>ans=solve(b);
	for(auto x:ans)if(x!=ans[0])printf("%d %d\n",x.fi,x.se);
	auto x=ans[0];
	printf("%d %d\n",x.fi,x.se);
	return 0;
}

Submission Info

Judge Result