CODE FESTIVAL 2016 Grand Final

Submission #1290936

Source codeソースコード

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
typedef pair<int,int> P;
vector<P> construct(vector<int> as){
	int N = as.size();
	if(N==4){
		vector<P> res;
		res.pb(P(1,0));
		res.pb(P(1,1));
		res.pb(P(0,1));
		res.pb(P(0,0));
		return res;
	}
	int s = -1;
	rep(i,N){
		if(as[i]==90 && as[(i+1)%N]==270) s=i;
	}
	vector<int> nas;
	for(int i=s-1;i<s-1+N;i++) if(i!=s&&i!=s+1) nas.pb(as[(i+N)%N]);
	vector<P> base = construct(nas);
	vector<P> res(N);

	rep(i,N-2){
		P p = base[i];
		if(i==0 || base[0].fs<p.fs) p.fs++;
		if(base[0].sc<p.sc) p.sc++;
		int id = (i==0?0:i+2);
		res[id] = p;
	}
	res[1] = P(res[0].fs,res[0].sc+1);
	res[2] = P(res[1].fs-1,res[1].sc);
	assert(res[2].fs==res[3].fs);
	// puts("--------");
	// show(res);
	// puts("--------");
	rotate(res.begin(),res.begin()+(N-s+1)%N,res.end());
	if(res[0].fs!=res[1].fs){
		rep(i,N) swap(res[i].fs,res[i].sc),res[i].fs*=-1;
	}
	assert(res[0].fs==res[1].fs);
	if(res[0].sc>res[1].sc){
		rep(i,N) res[i].fs*=-1, res[i].sc*=-1;
	}
	// show(as);
	// printf("erase %d,%d\n",s,(s+1)%N);
	// show(res);
	return res;
}
int main(){
	int N;
	vector<int> xs;
	cin>>N;
	int sum = 0;
	rep(i,N){
		int x;
		cin>>x;
		xs.pb(x);
		if(x==90) sum++;
		else sum--;
	}
	if(sum!=4){
		puts("-1");
		return 0;
	}
	vector<P> ans = construct(xs);
	rep(i,N) ans[i].fs += 5e8, ans[i].sc += 5e8;
	rep(i,N){
		cout<<ans[i].fs<<" "<<ans[i].sc<<endl;
	}
}

Submission

Task問題 I - 90 and 270
User nameユーザ名 025_sigma
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 1500
Source lengthソースコード長 2025 Byte
File nameファイル名
Exec time実行時間 8 ms
Memory usageメモリ使用量 2688 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - example0.txt,example1.txt
All 1500 / 1500 000.txt,001.txt,002.txt,003.txt,004.txt,005.txt,006.txt,007.txt,008.txt,009.txt,010.txt,011.txt,012.txt,013.txt,014.txt,015.txt,016.txt,017.txt,018.txt,019.txt,020.txt,021.txt,022.txt,023.txt,024.txt,025.txt,026.txt,027.txt,028.txt,029.txt,030.txt,031.txt,032.txt,033.txt,034.txt,035.txt,036.txt,037.txt,038.txt,039.txt,040.txt,041.txt,042.txt,043.txt,example0.txt,example1.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
000.txt AC 1 ms 256 KB
001.txt AC 1 ms 256 KB
002.txt AC 1 ms 256 KB
003.txt AC 5 ms 1408 KB
004.txt AC 2 ms 468 KB
005.txt AC 3 ms 640 KB
006.txt AC 4 ms 1024 KB
007.txt AC 2 ms 512 KB
008.txt AC 2 ms 384 KB
009.txt AC 3 ms 640 KB
010.txt AC 6 ms 1792 KB
011.txt AC 2 ms 256 KB
012.txt AC 3 ms 896 KB
013.txt AC 3 ms 768 KB
014.txt AC 2 ms 256 KB
015.txt AC 2 ms 384 KB
016.txt AC 4 ms 1152 KB
017.txt AC 1 ms 256 KB
018.txt AC 4 ms 896 KB
019.txt AC 2 ms 512 KB
020.txt AC 7 ms 2432 KB
021.txt AC 1 ms 256 KB
022.txt AC 7 ms 2304 KB
023.txt AC 8 ms 2688 KB
024.txt AC 8 ms 2688 KB
025.txt AC 8 ms 2688 KB
026.txt AC 8 ms 2688 KB
027.txt AC 8 ms 2688 KB
028.txt AC 8 ms 2688 KB
029.txt AC 8 ms 2688 KB
030.txt AC 8 ms 2688 KB
031.txt AC 8 ms 2688 KB
032.txt AC 8 ms 2688 KB
033.txt AC 8 ms 2688 KB
034.txt AC 8 ms 2688 KB
035.txt AC 8 ms 2688 KB
036.txt AC 8 ms 2688 KB
037.txt AC 8 ms 2688 KB
038.txt AC 8 ms 2688 KB
039.txt AC 8 ms 2688 KB
040.txt AC 8 ms 2688 KB
041.txt AC 8 ms 2688 KB
042.txt AC 8 ms 2688 KB
043.txt AC 1 ms 256 KB
example0.txt AC 1 ms 256 KB
example1.txt AC 1 ms 256 KB