QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#740220 | #9170. Cycle Game | ucup-team134 | TL | 2638ms | 33060kb | C++17 | 4.2kb | 2024-11-13 03:59:58 | 2024-11-13 03:59:58 |
Judging History
answer
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL)
#define ld long double
#define li __int128
using namespace std;
mt19937 rng(time(NULL));
const int N=3e5+5;
struct dsu{
vector<int> par,siz;
vector<pair<int,pair<int,int>>> old;
int cntComp,cntCompsnap;
bool activeSnap;
void reset(int n){
par.resize(n);
siz.resize(n);
iota(all(par),0);
fill(all(siz),1);
old.clear();
cntComp=n;
activeSnap=0;
}
void snapshot(){
old.clear();
cntCompsnap=cntComp;
activeSnap=1;
}
void goToSnapshot(){
for(auto p:old){
par[p.f]=p.s.f;
siz[p.f]=p.s.s;
}
old.clear();
cntComp=cntCompsnap;
}
inline int find(int tr){return tr==par[tr]?tr:find(par[tr]);}
inline void merge(int a,int b){
a=find(a);
b=find(b);
if(a==b)return;
cntComp--;
if(siz[a]>siz[b])swap(a,b);
if(activeSnap){
old.pb({a,{par[a],siz[a]}});
}
par[a]=b;
siz[b]+=siz[a];
}
}dsu;
vector<int> dx={1,1,1,0,-1,-1,-1,0},dy={1,0,-1,-1,-1,0,1,1};
int main()
{
ios;
int n,m,k;
cin>>n>>m>>k;
bool mx=0;
if(n==-1){
n=75000;
m=4;
k=3e5;
mx=1;
}
vector<pair<int,int>> ord;
int C=4000;
auto inside=[&](int x,int y){
return x>=0&&x<n&&y>=0&&y<m;
};
auto ind=[&](int x,int y){
return x*m+y;
};
auto onBorder=[&](int x,int y){
return x==0||y==0||x==n-1||y==m-1;
};
if(mx){
for(int i=0;i<n;i++)for(int j=0;j<m;j++)ord.pb({i,j});
shuffle(all(ord),rng);
}
else{
for(int i=0;i<k;i++){
int x,y;
if(mx){
x=1;
y=rng()%m+1;
}
else
cin >> x >> y;
x--;y--;
ord.pb({x,y});
}
}
vector<vector<bool>> on(n,vector<bool>(m));
vector<vector<int>> next(n,vector<int>(m));
int cnt8=0;
int cntOn=0;
auto add=[&](int i,int j){
for(int kk=0;kk<8;kk++){
int x=i+dx[kk],y=j+dy[kk];
if(inside(x,y)){
next[x][y]++;
if(next[x][y]==8)cnt8++;
}
}
cntOn++;
};
auto sub=[&](int i,int j){
for(int kk=0;kk<8;kk++){
int x=i+dx[kk],y=j+dy[kk];
if(inside(x,y)){
if(next[x][y]==8)cnt8--;
next[x][y]--;
}
}
cntOn--;
};
vector<bool> ok(k,1);
int cntDo=0;
ll resetTime=0;
for(int i=0;i<k;){
int ost=min(C,k-i);
int j=i+ost;
//printf("%i->%i\n",i,j);
for(int o=i;o<j;o++){
int x=ord[o].f,y=ord[o].s;
on[x][y]=1;
add(x,y);
}
C-=47;C=max(C,400);
ll st=clock();
dsu.reset(n*m+1);
for(int x=0;x<n;x++){
for(int y=0;y<m;y++){
if(!on[x][y]){
if(onBorder(x,y)){
dsu.merge(ind(x,y),n*m);
}
for(int kk=0;kk<4;kk++){
int xx=x+dx[kk],yy=y+dy[kk];
if(inside(xx,yy)&&!on[xx][yy]){
dsu.merge(ind(x,y),ind(xx,yy));
}
}
}
}
}
resetTime+=clock()-st;
cntDo++;
//printf("CntComp: %i\n",dsu.cntComp);
int cntBack=0;
while(1){
if(dsu.cntComp-cntOn==1&&cnt8==0){ // everything is ok
break;
}
cntBack++;
dsu.snapshot();
for(int o=j-1;o>=i-1;o--){
assert(o!=i-1);
int x=ord[o].f,y=ord[o].s;
assert(on[x][y]);
on[x][y]=0;
sub(x,y);
if(onBorder(x,y)){
dsu.merge(ind(x,y),n*m);
}
for(int kk=0;kk<8;kk++){
int xx=x+dx[kk],yy=y+dy[kk];
if(inside(xx,yy)&&!on[xx][yy]){
dsu.merge(ind(x,y),ind(xx,yy));
}
}
if(dsu.cntComp-cntOn==1&&cnt8==0){
ok[o]=0;
dsu.goToSnapshot();
for(int p=o+1;p<j;p++){
on[ord[p].f][ord[p].s]=1;
add(ord[p].f,ord[p].s);
}
if(onBorder(x,y)){
dsu.merge(ind(x,y),n*m);
}
for(int kk=0;kk<8;kk++){
int xx=x+dx[kk],yy=y+dy[kk];
if(inside(xx,yy)&&!on[xx][yy]){
dsu.merge(ind(x,y),ind(xx,yy));
}
}
break;
}
}
}
/*if(cntBack<10){
C*=1.3;
}
else{
C/=1.5;
C=max(C,600);
}*/
i=j;
}
if(mx)
printf("%i\n",cntDo),printf("%lld\n",resetTime),printf("C: %i\n",C);
for(int i=0;i<k;i++){
printf(ok[i]?"1":"0");
}
printf("\n");
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3748kb
input:
4 3 7 2 1 2 2 2 3 3 1 3 2 4 1 4 2
output:
1111111
result:
ok "1111111"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
3 3 8 1 1 1 2 1 3 2 3 3 3 3 2 3 1 2 1
output:
11111110
result:
ok "11111110"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
10 10 7 9 1 6 6 3 8 8 7 5 10 1 7 1 2
output:
1111111
result:
ok "1111111"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3964kb
input:
9 10 50 1 9 1 6 2 3 3 1 7 4 9 4 1 3 2 5 9 2 7 9 5 6 8 10 9 5 5 5 4 10 9 7 5 9 3 2 4 5 1 1 4 7 3 6 2 8 4 3 8 6 5 10 4 8 5 4 7 2 9 6 4 2 7 8 5 2 3 5 9 1 6 1 1 5 9 9 5 8 6 3 8 8 8 4 7 7 7 1 3 7 2 2 3 10 6 9 8 3 7 6
output:
11111111111111111111111111111111111111111111111111
result:
ok "11111111111111111111111111111111111111111111111111"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
3 5 11 1 5 2 4 1 2 1 3 3 3 3 1 3 4 2 3 1 4 2 1 2 5
output:
11111111111
result:
ok "11111111111"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3964kb
input:
7 9 12 7 3 2 3 6 2 2 2 4 2 2 8 5 7 4 4 6 8 2 7 7 2 1 9
output:
111111111111
result:
ok "111111111111"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3960kb
input:
1 4 1 1 2
output:
1
result:
ok "1"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
9 8 67 5 5 8 3 9 5 7 4 5 1 9 3 4 2 2 5 1 7 7 8 7 2 8 5 6 1 8 8 4 4 5 4 1 5 3 4 6 7 2 3 3 7 5 7 2 4 2 7 1 3 7 3 2 8 6 6 6 2 6 3 7 5 9 6 7 6 3 6 1 1 6 4 3 1 5 3 8 7 2 1 4 1 8 4 8 6 3 5 5 8 1 6 1 2 4 6 9 4 1 4 3 3 4 8 8 1 4 7 9 8 3 8 6 5 6 8 3 2 2 2 7 1 9 2 4 3 1 8 4 5 8 2 7 7
output:
1111111111111111111111111111111111111111111110010101101000101101101
result:
ok "111111111111111111111111111111...1111111110010101101000101101101"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3968kb
input:
3 10 3 3 9 2 5 2 7
output:
111
result:
ok "111"
Test #10:
score: 0
Accepted
time: 38ms
memory: 33060kb
input:
222212 1 21562 105762 1 167947 1 127551 1 117618 1 174844 1 139867 1 156729 1 30554 1 54488 1 151832 1 132914 1 109432 1 212091 1 136499 1 17818 1 48806 1 95752 1 66607 1 39930 1 23054 1 160823 1 169054 1 96680 1 150677 1 52895 1 93103 1 118079 1 79155 1 194811 1 141874 1 138763 1 2600 1 121471 1 17...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok "111111111111111111111111111111...1111111111111111111111111111111"
Test #11:
score: 0
Accepted
time: 72ms
memory: 6348kb
input:
1 167058 126088 1 15282 1 63796 1 77270 1 88793 1 42787 1 129851 1 34468 1 74525 1 121105 1 157182 1 92736 1 102044 1 11284 1 23439 1 142720 1 128610 1 27437 1 105575 1 130827 1 152824 1 76358 1 152954 1 65509 1 139802 1 66299 1 108943 1 140446 1 112411 1 95814 1 115750 1 9667 1 55383 1 89323 1 6734...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok "111111111111111111111111111111...1111111111111111111111111111111"
Test #12:
score: 0
Accepted
time: 1967ms
memory: 5340kb
input:
9 12788 86384 4 11931 2 8183 1 5816 7 10320 8 5754 4 10778 4 12280 7 12746 1 4699 3 7876 4 3044 2 4903 9 10252 8 10512 7 6546 8 1338 5 9700 1 9833 6 11315 2 4067 7 9350 9 8200 2 1718 1 2542 2 4596 9 367 5 12426 1 12166 5 7652 4 2316 9 1946 3 6187 4 3306 1 63 8 4132 3 12491 2 3951 8 4169 7 11801 9 46...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok "111111111111111111111111111111...0010111100011000000100110101100"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
10 6 58 7 3 1 5 9 2 10 4 1 2 1 6 9 6 5 4 8 2 9 3 5 1 4 5 7 4 10 1 10 3 5 3 4 3 6 5 1 4 7 2 10 6 8 3 5 6 9 4 2 2 1 1 6 4 3 5 3 2 6 2 3 6 8 1 8 4 8 5 7 5 6 1 4 4 3 4 3 1 7 1 4 1 2 4 6 6 9 5 7 6 2 1 5 5 10 2 2 5 4 2 2 6 10 5 9 1 4 6 5 2 6 3 1 3 8 6
output:
1111111111111111111111111111111101111111111011011001000000
result:
ok "1111111111111111111111111111111101111111111011011001000000"
Test #14:
score: 0
Accepted
time: 0ms
memory: 6640kb
input:
23660 2 4698 10158 1 1229 1 51 2 10559 2 15495 2 19343 1 18458 1 19633 2 23151 1 11738 2 21366 1 12968 2 10474 1 10552 2 8067 2 7125 2 14643 1 7579 2 21608 2 7067 2 20400 1 14397 2 21474 2 8294 2 1332 1 18105 1 2285 1 1223 1 13429 2 18580 2 11156 2 5498 1 6830 1 8848 2 21334 2 11946 1 10177 1 5349 1...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok "111111111111111111111111111111...1111111111111111111111111111111"
Test #15:
score: 0
Accepted
time: 1626ms
memory: 4292kb
input:
51 732 29706 14 458 6 600 18 452 43 262 24 685 51 192 14 248 50 672 16 65 45 191 25 196 1 447 4 574 32 493 16 100 39 715 17 397 37 644 32 580 32 622 22 160 20 694 29 120 30 302 7 283 18 290 51 420 20 553 42 681 11 724 26 528 50 497 46 500 3 534 36 58 42 167 18 534 1 654 50 276 37 386 19 649 14 41 8 ...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok "111111111111111111111111111111...0100001111101110110110000010000"
Test #16:
score: 0
Accepted
time: 1247ms
memory: 17132kb
input:
75000 4 225000 71753 3 13211 2 61737 3 59039 3 3674 3 50461 4 12758 3 69966 1 57525 1 42178 1 15054 1 66939 2 2798 4 74983 2 7250 2 2247 4 11438 1 67858 4 66527 2 21625 2 14111 2 28737 1 7431 4 11317 3 47421 2 51295 4 39591 4 20811 3 51582 3 47874 2 3238 2 10987 3 1225 1 58741 4 2141 3 35454 4 5021 ...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok "111111111111111111111111111111...1101011111100100010101000000000"
Test #17:
score: 0
Accepted
time: 1254ms
memory: 20036kb
input:
100000 3 240000 63826 2 25561 1 24122 3 56762 3 66822 2 24467 2 5419 1 59533 2 71406 2 62274 1 63084 1 33262 3 16614 2 71724 1 99182 1 3574 3 2804 2 40022 2 90379 1 44898 2 59169 3 55663 1 79971 2 30606 3 58613 3 38992 3 51702 1 10168 3 44411 3 39048 1 25384 2 276 1 68607 1 34137 1 72641 2 92427 1 9...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok "111111111111111111111111111111...0101001000001000101001011110010"
Test #18:
score: 0
Accepted
time: 1820ms
memory: 15292kb
input:
60000 5 250000 19905 3 6687 2 7727 4 23854 3 1329 4 45419 4 15116 1 35612 4 11560 1 16969 5 43328 4 30175 2 1587 5 15890 1 53896 3 43465 4 26642 2 3443 5 6697 5 6489 3 44351 2 48037 2 39926 5 974 1 20783 2 51437 4 31394 2 33663 2 26261 5 49301 4 2074 1 16999 4 48098 5 28754 4 27961 3 614 5 57608 2 5...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok "111111111111111111111111111111...0010100101111000100000011001011"
Test #19:
score: 0
Accepted
time: 1547ms
memory: 20896kb
input:
100000 3 270000 50999 2 78476 3 21423 1 26134 3 69234 1 48259 3 40043 1 92586 1 96544 3 65679 1 63139 1 79464 2 76129 3 3836 3 65093 1 81997 3 13905 2 82341 2 32201 1 42796 2 69216 3 14753 3 50176 3 66724 2 21607 3 9619 2 96579 1 59856 2 5086 1 89747 1 4122 3 8806 3 57529 2 6476 3 6689 2 97261 1 936...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok "111111111111111111111111111111...0000011010000000010100010001010"
Test #20:
score: 0
Accepted
time: 2638ms
memory: 13524kb
input:
29997 10 272700 22251 10 4359 10 3780 4 23168 10 19310 8 784 2 21855 1 19914 4 279 9 26868 6 11534 3 17252 8 10865 2 15782 3 10134 4 17047 4 8318 5 11552 4 21333 1 2023 10 17397 5 13151 3 21068 3 1171 3 21112 4 23374 4 289 8 9248 3 19337 3 10005 7 16909 2 14103 5 3098 8 23534 3 7782 1 4765 7 10294 8...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok "111111111111111111111111111111...1100000010000000010000000100010"
Test #21:
score: 0
Accepted
time: 1173ms
memory: 11588kb
input:
30000 10 180008 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 40 1 41 1 42 1 43 1 44 1 45 1 46 1 47 1 48 1 49 1 50 1 51 1 52 1 53 1 54 1 55 1 56 1 57 1 58 1 59 ...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok "111111111111111111111111111111...1111110111111101111111011111111"
Test #22:
score: 0
Accepted
time: 1086ms
memory: 20068kb
input:
100000 3 250001 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 40 1 41 1 42 1 43 1 44 1 45 1 46 1 47 1 48 1 49 1 50 1 51 1 52 1 53 1 54 1 55 1 56 1 57 1 58 1 59 ...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok "111111111111111111111111111111...0000000000000000000000000000001"
Test #23:
score: 0
Accepted
time: 208ms
memory: 8204kb
input:
300 1000 151298 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 40 1 41 1 42 1 43 1 44 1 45 1 46 1 47 1 48 1 49 1 50 1 51 1 52 1 53 1 54 1 55 1 56 1 57 1 58 1 59 ...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok "111111111111111111111111111111...1111111111111111111111111111111"
Test #24:
score: -100
Time Limit Exceeded
input:
1000 300 300000 1 1 1 3 1 5 1 7 1 9 1 11 1 13 1 15 1 17 1 19 1 21 1 23 1 25 1 27 1 29 1 31 1 33 1 35 1 37 1 39 1 41 1 43 1 45 1 47 1 49 1 51 1 53 1 55 1 57 1 59 1 61 1 63 1 65 1 67 1 69 1 71 1 73 1 75 1 77 1 79 1 81 1 83 1 85 1 87 1 89 1 91 1 93 1 95 1 97 1 99 1 101 1 103 1 105 1 107 1 109 1 111 1 1...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...