QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#348509 | #1827. Token Game | LaStataleBlue | AC ✓ | 603ms | 116840kb | C++23 | 2.6kb | 2024-03-09 19:08:14 | 2024-03-09 19:08:15 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 301;
vector col(N,vector(N,bitset<N>(0)));
vector sol(N,vector(N,vector(N,0)));
void calc(){
for(int i=0;i<N;i++){
vector tmp(N,bitset<N>(0));
for(int j=0;j<N;j++){
bitset<N> prec(0);
for(int k=0;k<N;k++){
int p1=-1,p2=-1;
if(k==i-1 || k==i+1){
p1=j;
}else if(k==i){
p1=j-1;
p2=j+1;
}else{
p1 = (~(tmp[k]|col[j][k]|prec))._Find_first();
}
sol[i][j][k]=p1;
if(p1>=0 && p1<N-1){
col[j][k][p1]=1;
tmp[k][p1]=1;
prec[p1]=1;
}
if(p2>=0 && p1<N-1){
col[j][k][p2]=1;
tmp[k][p2]=1;
prec[p2]=1;
}
}
}
}
/*
const int X = 5, Y = 7;
for(int i=0;i<20;i++){
for(int j=0;j<20;j++){
if(i==X && j==Y){
cout<<"X";
}else if(abs(i-X)+abs(j-Y)==1){
cout<<"P";
}else if(abs(i-X)<=1 || abs(j-Y)<=1){
cout<<"_";
}else if(sol[X][Y][i]==j){
cout<<"P";
}else{
cout<<"_";
}
cout<<" ";
}
cout<<"\n";
}*/
}
int check(int X,int Y,int i,int j){
if(abs(i-X)+abs(j-Y)==1){
return 1;
}else if(abs(i-X)<=1 || abs(j-Y)<=1){
return 0;
}else if(sol[X][Y][i]==j){
return 1;
}else{
return 0;
}
}
void solve([[maybe_unused]]int t){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
x1--;
y1--;
x2--;
y2--;
int ans=0;
for(int i=x1-1;i>=0;i--){
if(i==x2 && y1==y2)break;
ans+=check(i,y1,x2,y2);
}
for(int i=y1-1;i>=0;i--){
if(i==y2 && x1==x2)break;
ans+=check(x1,i,x2,y2);
}
for(int i=x2-1;i>=0;i--){
if(i==x1 && y1==y2)break;
ans+=check(x1,y1,i,y2);
}
for(int i=y2-1;i>=0;i--){
if(i==y1 && x1==x2)break;
ans+=check(x1,y1,x2,i);
}
cout<<ans<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
calc();
int t=1;
cin>>t;
for(int i=1;i<=t;i++)solve(i);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 215ms
memory: 116840kb
input:
5 6 6 6 3 6 6 2 2 1 6 3 1 3 6 1 3 6 3 1 5
output:
3 0 1 1 0
result:
ok 5 number(s): "3 0 1 1 0"
Test #2:
score: 0
Accepted
time: 603ms
memory: 116716kb
input:
100000 215 233 28 258 15 243 61 148 172 28 96 37 15 132 62 27 41 186 255 54 145 192 249 263 274 70 185 197 50 101 202 230 256 11 285 19 149 268 163 107 177 201 216 126 65 17 105 263 143 148 2 230 40 128 259 176 183 192 293 169 281 59 240 229 257 157 126 182 161 51 164 14 149 191 227 102 55 14 267 19...
output:
3 1 1 1 1 2 2 3 1 1 3 1 1 1 1 3 3 1 1 1 1 1 1 2 1 1 1 2 1 1 3 1 3 1 1 2 1 1 1 3 4 1 1 3 1 2 2 1 1 1 3 1 1 1 3 1 1 1 1 2 3 1 3 1 1 3 1 3 3 2 1 2 3 3 1 1 1 2 2 1 2 1 3 1 1 1 1 1 2 1 4 1 1 1 3 3 1 1 1 1 2 1 1 1 1 3 2 3 2 1 1 3 1 1 1 1 2 1 1 2 3 1 3 1 1 1 2 3 3 1 2 3 1 1 1 1 1 2 3 2 2 2 1 1 3 1 1 1 2 2 ...
result:
ok 100000 numbers