Submission #1727345
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount
#define INF INT_MAX/3
struct UnionFind{
vector<int> v;
UnionFind(int n) : v(n, -1) {}
void init(){ for(int i = 0;i < v.size();i++)v[i]=-1; }
int find(int x) { return v[x] < 0 ? x : v[x] = find(v[x]); }
bool unite(int x, int y) {
x = find(x); y = find(y);
if (x == y) return false;
if (-v[x] < -v[y]) swap(x, y);
v[x] += v[y]; v[y] = x;
return true;
}
bool root(int x) { return v[x] < 0; }
bool same(int x, int y) { return find(x) == find(y); }
int size(int x) { return -v[find(x)]; }
};
ll n;
ll dd[]={-1,0,1,0,-1};
vector<P> res;
ll tot;
bool valid(ll i,ll j){
return i>=0&&i<n&&j>=0&&j<n;
}
int main(){
cin>>n;
rep(i,n)rep(j,n){
if((i+j)%2==0)continue;
tot++;
}
UnionFind uf(n*n);
rep(hoge,7){
rep(i,n)rep(j,n){
if((i+j)%2==0)continue;
bool ok=true;
ll cnt=0;
rep(d1,4)repl(d2,d1+1,4){
ll ni1=i+dd[d1],nj1=j+dd[d1+1];
ll ni2=i+dd[d2],nj2=j+dd[d2+1];
if(!valid(ni1,nj1)||!valid(ni2,nj2)||(ni1==ni2&&nj1==nj2))continue;
if(!uf.same(ni1*n+nj1,ni2*n+nj2))cnt++;
}
if(cnt>=7-hoge){
res.push_back(P(i,j));
rep(d1,4)rep(d2,4){
ll ni1=i+dd[d1],nj1=j+dd[d1+1];
ll ni2=i+dd[d2],nj2=j+dd[d2+1];
if(!valid(ni1,nj1)||!valid(ni2,nj2))continue;
uf.unite(ni1*n+nj1,ni2*n+nj2);
}
}
}
}
printf("%lld\n", (ll)res.size());
rep(i,res.size())printf("%lld %lld\n", res[i].se,res[i].fi);
return 0;
}
Submission Info
Submission Time |
|
Task |
J - Connected Checkerboard |
User |
yamad |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
2193 Byte |
Status |
AC |
Exec Time |
208 ms |
Memory |
10096 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
100 / 100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt |
All |
sample_01.txt, sample_02.txt, sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
subtask1_01.txt |
AC |
10 ms |
640 KB |
subtask1_02.txt |
AC |
1 ms |
256 KB |
subtask1_03.txt |
AC |
25 ms |
1276 KB |
subtask1_04.txt |
AC |
11 ms |
768 KB |
subtask1_05.txt |
AC |
64 ms |
2804 KB |
subtask1_06.txt |
AC |
105 ms |
4340 KB |
subtask1_07.txt |
AC |
17 ms |
1020 KB |
subtask1_08.txt |
AC |
110 ms |
4468 KB |
subtask1_09.txt |
AC |
95 ms |
4212 KB |
subtask1_10.txt |
AC |
203 ms |
9712 KB |
subtask1_11.txt |
AC |
199 ms |
9968 KB |
subtask1_12.txt |
AC |
194 ms |
9712 KB |
subtask1_13.txt |
AC |
203 ms |
9840 KB |
subtask1_14.txt |
AC |
198 ms |
9712 KB |
subtask1_15.txt |
AC |
193 ms |
9456 KB |
subtask1_16.txt |
AC |
190 ms |
8560 KB |
subtask1_17.txt |
AC |
191 ms |
9072 KB |
subtask1_18.txt |
AC |
193 ms |
10096 KB |
subtask1_19.txt |
AC |
203 ms |
8688 KB |
subtask1_20.txt |
AC |
208 ms |
9584 KB |