Submission #26515200

Source Code Expand

#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;

typedef pair<int,int>P;
#define F first
#define S second

unsigned long long xor128() {
    static unsigned long long rx = 123456789, ry = 362436069, rz = 521288629, rw = 88675123;
    unsigned long long rt = (rx ^ (rx << 11));
    rx = ry;
    ry = rz;
    rz = rw;
    return (rw = (rw ^ (rw >> 19)) ^ (rt ^ (rt >> 8)));
}
std::chrono::system_clock::time_point start;
std::chrono::system_clock::time_point owari;

double gettime(){
	owari = std::chrono::system_clock::now();

// erapsed = ms
double elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(owari-start).count();
return elapsed;	
}

struct UnionFind{
  int n;
  vector<int> ran,p,cnt;
  UnionFind(){}
  UnionFind(int sz):n(sz),ran(sz,1),p(sz,0){iota(p.begin(),p.end(),0);}
  int find(int x){
    return (x==p[x]?x:p[x]=find(p[x]));
  }
  bool same(int x,int y){
    return find(x)==find(y);
  }
  void unite(int x,int y){
    x=find(x);y=find(y);
    if(x==y) return;
    if(ran[x]<ran[y]) swap(x,y);
    ran[x]+=ran[y];
    p[y]=x;
  }
  int sum(int x){
    return ran[find(x)];
  }
};

int N,K,B;
int my[1000];
int mx[1000];
int ch[1000];
int cw[1000];
int cc[1000];
string S[100][50];

struct POINT{
int x,y,k;
};

vector<bitset<50*50> > mask_tmp,mask;
vector<POINT>mask_point;
vector<int>mask_cnt;
vector<int>mask_cost;
bitset<50*50> M;

bitset<50*50> BIT;
unordered_set<int>used;
int sum=0;
int cost = 0;
int costB = 0;
vector<int>tmp;

int ind[20000];

void INIT(){
	sum = 0;
	cost = 0;
	BIT.reset();
	for(int i=0;i<mask.size();i++) if(used.count(i)) {
		if(sum == K) break;
		if((BIT&mask[i]).any()) continue;
		sum += mask_cnt[i];
		cost += mask_cost[i];
		BIT |= mask[i];
		used.insert(i);
	}

}

void Finsert(){
	for(int i2=0;i2<mask.size();i2++){
		int i=ind[i2];
		if(sum == K) break;
		if((BIT&mask[i]).any()) continue;
		sum += mask_cnt[i];
		cost += mask_cost[i];
		BIT |= mask[i];
		used.insert(i);

	}
}
int dx[]={0,1,0,-1};
int dy[]={-1,0,1,0};
void Union(){
	costB = 0;
	UnionFind U(50*50);
	r(i,50){
		r(j,50){
			if(BIT.test(i*50+j)==false)continue;
			r(k,4){
				int y=i+dy[k];
				int x=j+dx[k];
				if(y<0||x<0||y>=N||x>=N) continue;
				if(BIT.test(y*50+x)==false) continue;
				U.unite(y*50+x , i*50+j);
			}
		}
	}
	tmp.clear();
	while(1){
		set<int>st;
		vector<P>sz;
		r(i,2500) if(BIT.test(i)) {
			st.insert(U.find(i));
		}
		r(i,2500) if(BIT.test(i)) {
			sz.emplace_back(P(U.sum(i),i));
		}
		sort(sz.begin(),sz.end());


		if(st.size()==1)break;

		int a = U.find(sz[0].S);
		int MIN = 1e9;
		vector<int>pa;
		int cnt=0;
		queue<int>q;
		unordered_map<int,int>qm;
		unordered_map<int,int>path;

		r(i,2500)if(U.find(i)==a){
			
			q.push(i);
			qm[i]=1;
			path[i] = -1;
		}
		{
			while(!q.empty()){
				int i = q.front()/50;
				int j = q.front()%50;q.pop();
				r(k,4){
					int y=i+dy[k];
					int x=j+dx[k];
					if(y<0||x<0||y>=N||x>=N) continue;
					if(qm.count(y*50+x))continue;
					if(MIN <= qm[i*50+j] + 1) continue;
					q.push(y*50+x);
					qm[y*50+x] = qm[i*50+j] + 1;
					path[y*50+x] = i*50+j;
					if( U.find(y*50+x)!=a && st.count(U.find(y*50+x)) ){
						MIN = min(MIN,qm[y*50+x]);
						int t = y*50+x;
						pa.clear();
						while(t!=-1){
							pa.emplace_back(t);
							t = path[t];
						}
						goto L;
					}
				}
			}
			L:;
			
		}

		for(int i=0;i<pa.size()-1;i++){
			if(i)tmp.emplace_back(pa[i]);
			costB++;
			U.unite(pa[i],pa[i+1]);
		}
		costB--;

	}

}




void solve(){
	r(i,20000)ind[i] = i;

	int maxscore = 1e9;
	unordered_set<int>aused;
	vector<int>atmp;
	while(gettime() <= 1990){
		vector<P>vect;
		r(i,xor128()%100 + 50){
			int a=xor128()%mask.size();
			int q = xor128()%1000 +20;
			int b=a+(xor128()%q)-q/2;
			if(b<0)b=0;
			if(b>=mask.size())b=mask.size()-1;
			vect.emplace_back(P(a,b));
		}
		r(i,vect.size())swap(ind[vect[i].F],ind[vect[i].S]);

		INIT();
		//cerr<<costB*15 + cost<<endl;
		Finsert();
		//cerr<<costB*15 + cost<<endl;
		Union();
		//cerr<<costB*15 + cost<<endl<<endl<<endl;
		if(maxscore > costB*15 + cost){
			maxscore = costB*15 + cost;
			aused = used;
			atmp = tmp;
			cerr<<maxscore<<endl;
		}
		else{
			for(int i=vect.size()-1;i>=0;i--){
				swap(ind[vect[i].F],ind[vect[i].S]);
			}
		}


		used.clear();
		/*vector<int>vec;
		for(auto &e:used){
			vec.emplace_back(e);
		}
		int x=xor128()% vec.size();
		r(i,x){
			int t=vec[xor128()%vec.size()];
			used.erase(t);
		}*/
	}

	cout<<atmp.size()+aused.size()<<endl;
	for(auto &i:aused){
		cout<<mask_point[i].k+1<<' '<<mask_point[i].y<<' '<<mask_point[i].x<<endl;
	}
	for(auto &e:atmp){
		cout<<1<<' '<<e/50<<' '<<e%50<<endl;
	}
}

void make(){
	r(i,K){
		M.set(my[i]*50 + mx[i]);
	}
	vector<P>vec;
	int cnt=0;
	vector<POINT>OOO;
	r(k,B){
		r(i,N-ch[k]+1){
			r(j,N-cw[k]+1){
				bitset<50*50> b;
				r(I,ch[k]){
					r(J,cw[k]){
						if(S[k][I][J]!='#') continue;
						b.set((i+I)*50 + j+J);
					}
				}
				if((M&b).any() == false) continue;
				mask_tmp.emplace_back(b);
				vec.emplace_back(P(-(M&b).count(),cc[k]*10000 + cnt));
				POINT PO;
				PO.x = j;
				PO.y = i;
				PO.k = k;
				OOO.emplace_back(PO);
				cnt++;
			}
		}
	}
	sort(vec.begin(),vec.end());
	r(i,vec.size()){
		int cnt = vec[i].S%10000;
		int ccc = vec[i].S/10000;
		mask.push_back(mask_tmp[cnt]);
		mask_cnt.emplace_back(vec[i].F * -1);
		mask_cost.emplace_back(ccc);
		mask_point.emplace_back(OOO[cnt]);

	}
}

int main(){
	start = std::chrono::system_clock::now();
	cin>>N>>K>>B;
	r(i,K){
		cin>>my[i]>>mx[i];
	}
	r(i,B){
		cin>>ch[i];
		cin>>cw[i];
		cin>>cc[i];
		r(j,ch[i]){
			cin>>S[i][j];
		}
	}
	make();
	solve();
	cerr<<"EndTime: "<<gettime()<<endl;
}

Submission Info

Submission Time
Task C - Polyomino Connection C
User c7c7
Language C++ (GCC 9.2.1)
Score 2067513
Code Size 5977 Byte
Status AC
Exec Time 2000 ms
Memory 10048 KiB

Compile Error

./Main.cpp: In function ‘void INIT()’:
./Main.cpp:82:15: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::bitset<2500> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   82 |  for(int i=0;i<mask.size();i++) if(used.count(i)) {
      |              ~^~~~~~~~~~~~
./Main.cpp: In function ‘void Finsert()’:
./Main.cpp:94:17: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::bitset<2500> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   94 |  for(int i2=0;i2<mask.size();i2++){
      |               ~~^~~~~~~~~~~~
./Main.cpp: In function ‘void Union()’:
./Main.cpp:180:16: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  180 |   for(int i=0;i<pa.size()-1;i++){
      |               ~^~~~~~~~~~~~
./Main.cpp:140:7: warning: unused variable ‘cnt’ [-Wunused-variable]
  140 |   int cnt=0;
      |       ^~~
./Main.cpp: In function ‘void solve()’:
./Main.cpp:2:29: warning: comparison of integer expressions of different signedness: ‘int’ and ‘long long unsigned int’ [-Wsign-compare]
    2 | #define r(i,n) for(int i=0;i<n;i++)
......
  202 |   r(i,xor128()%100 + 50){
      |     ~~~~~~~~~~~~~~~~~~~      
./Main.cpp:202:3: note: in expansion of macro ‘r’
  202 |   r(i,xor128()%100 + 50){
      |   ^
./Main.cpp:207:8: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::bitset<2500> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  207 |    if(b>=mask.size())b=mask.size()-1;
      |       ~^~~~~~~~~~~~~
./Main.cpp:2:29: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
    2 | #define r(i,n) for(int i=0;i<n;i++)
......
  210 |   r(i,vect.size())swap(ind[vect[i].F...

Judge Result

Set Name test_ALL
Score / Max Score 2067513 / 10000000000
Status
AC × 50
Set Name Test Cases
test_ALL test_0000.txt, test_0001.txt, test_0002.txt, test_0003.txt, test_0004.txt, test_0005.txt, test_0006.txt, test_0007.txt, test_0008.txt, test_0009.txt, test_0010.txt, test_0011.txt, test_0012.txt, test_0013.txt, test_0014.txt, test_0015.txt, test_0016.txt, test_0017.txt, test_0018.txt, test_0019.txt, test_0020.txt, test_0021.txt, test_0022.txt, test_0023.txt, test_0024.txt, test_0025.txt, test_0026.txt, test_0027.txt, test_0028.txt, test_0029.txt, test_0030.txt, test_0031.txt, test_0032.txt, test_0033.txt, test_0034.txt, test_0035.txt, test_0036.txt, test_0037.txt, test_0038.txt, test_0039.txt, test_0040.txt, test_0041.txt, test_0042.txt, test_0043.txt, test_0044.txt, test_0045.txt, test_0046.txt, test_0047.txt, test_0048.txt, test_0049.txt
Case Name Status Exec Time Memory
test_0000.txt AC 2000 ms 9716 KiB
test_0001.txt AC 1995 ms 9780 KiB
test_0002.txt AC 1995 ms 10012 KiB
test_0003.txt AC 1995 ms 9872 KiB
test_0004.txt AC 1994 ms 10000 KiB
test_0005.txt AC 1995 ms 9672 KiB
test_0006.txt AC 1994 ms 9648 KiB
test_0007.txt AC 1995 ms 10016 KiB
test_0008.txt AC 1994 ms 9620 KiB
test_0009.txt AC 1994 ms 10004 KiB
test_0010.txt AC 1996 ms 9624 KiB
test_0011.txt AC 1994 ms 9752 KiB
test_0012.txt AC 1995 ms 10012 KiB
test_0013.txt AC 1995 ms 10004 KiB
test_0014.txt AC 1996 ms 9740 KiB
test_0015.txt AC 1994 ms 9680 KiB
test_0016.txt AC 1997 ms 9964 KiB
test_0017.txt AC 1995 ms 9724 KiB
test_0018.txt AC 1997 ms 10044 KiB
test_0019.txt AC 1994 ms 9860 KiB
test_0020.txt AC 1996 ms 9716 KiB
test_0021.txt AC 1994 ms 9740 KiB
test_0022.txt AC 1995 ms 9736 KiB
test_0023.txt AC 1995 ms 9940 KiB
test_0024.txt AC 1995 ms 9780 KiB
test_0025.txt AC 1994 ms 9884 KiB
test_0026.txt AC 1995 ms 9696 KiB
test_0027.txt AC 1995 ms 9664 KiB
test_0028.txt AC 1994 ms 9728 KiB
test_0029.txt AC 1994 ms 9684 KiB
test_0030.txt AC 1995 ms 9740 KiB
test_0031.txt AC 1999 ms 9936 KiB
test_0032.txt AC 1994 ms 9604 KiB
test_0033.txt AC 1995 ms 10016 KiB
test_0034.txt AC 1994 ms 9716 KiB
test_0035.txt AC 1993 ms 9676 KiB
test_0036.txt AC 1996 ms 10040 KiB
test_0037.txt AC 1994 ms 9676 KiB
test_0038.txt AC 1995 ms 10048 KiB
test_0039.txt AC 1995 ms 9936 KiB
test_0040.txt AC 1995 ms 10016 KiB
test_0041.txt AC 1995 ms 9716 KiB
test_0042.txt AC 1995 ms 9712 KiB
test_0043.txt AC 1995 ms 9668 KiB
test_0044.txt AC 1994 ms 9984 KiB
test_0045.txt AC 1995 ms 10048 KiB
test_0046.txt AC 1994 ms 9776 KiB
test_0047.txt AC 1994 ms 10040 KiB
test_0048.txt AC 1996 ms 9664 KiB
test_0049.txt AC 1995 ms 10012 KiB