QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#739268 | #9469. Chinese Checkers | Midsummer | WA | 54ms | 3820kb | C++14 | 6.1kb | 2024-11-12 21:17:22 | 2024-11-12 21:17:38 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define endl '\n'
#define pai acos(-1.0)
using namespace std;
int mp[25][25];
int vis[25][25];
int len[20] = {0,1,2,3,4,13,12,11,10,9,10,11,12,13,4,3,2,1};
int dy[20] = {0,0,0,0,4,-1,-1,-1,-1,0,0,0,0,-5,-1,-1,-1,0};
void init()
{
memset(mp,0,sizeof mp);
memset(vis,0,sizeof vis);
for(int i = 1; i <= 4; i++)
{
for(int j = 1; j <= i; j++)
{
mp[i][j] = 1; vis[i][j] = 1;
}
}
for(int i = 5; i <= 8; i++)
{
for(int j = 1; j <= 9-i; j++)
{
mp[i][j] = 6; vis[i][j] = 6; mp[i][len[i]-j+1] = 4; vis[i][len[i]-j+1] = 4;
}
}
for(int i = 10; i <= 13; i++)
{
for(int j = 1; j <= i-10+1; j++)
{
mp[i][j] = 3; vis[i][j] = 3; mp[i][len[i]-j+1] = 5; vis[i][len[i]-j+1] = 5;
}
}
for(int i = 14; i <= 17; i++)
{
for(int j = 1; j <= 17-i+1; j++)
{
mp[i][j] = 2; vis[i][j] = 2;
}
}
}
pii pos(string op,int x,int y)
{
pii ans = {0,0};
if(op.size() == 1)
{
if(op[0] == 'L')
ans.second = -1;
else if(op[0] == 'R')
ans.second = 1;
}
else
{
if(op[0] == 'U')
{
ans.first = -1;
ans.second -= dy[x-1];
if(op[1] == 'L')
ans.second --;
}
else if(op[0] == 'L')
{
ans.first = 1;
ans.second = dy[x];
if(op[1] == 'R')
ans.second++;
}
}
return ans;
}
bool check(vector<int>x)
{
vector<int>y = x;
reverse(y.begin(),y.end());
return x == y;
}
bool obe(int x,int y)
{
if((mp[x][y] == 1 || mp[x][y] == 2) && (vis[x][y] == 1 || vis[x][y] == 2 || vis[x][y] == 0))
return 1;
if((mp[x][y] == 3 || mp[x][y] == 4) && (vis[x][y] == 3 || vis[x][y] == 4 || vis[x][y] == 0))
return 1;
if((mp[x][y] == 5 || mp[x][y] == 6) && (vis[x][y] == 5 || vis[x][y] == 6 || vis[x][y] == 0))
return 1;
return 0;
}
struct node
{
int x;
int y;
};
bool cmp(node a,node b)
{
if(a.x != b.x)
return a.x < b.x;
else
return a.y < b.y;
}
void solve()
{
int n;
while(cin >> n)
{
init();
// for(int i = 1; i <= 17; i++)
// {
// for(int j = 1; j <= 17; j++)
// {
// cout << mp[i][j];
// }
// cout << endl;
// }
int playtimes = 1;
while(n--)
{
int x,y;
string dir;
cin >> x >> y >> dir;
if(playtimes++ != mp[x][y])
{
if(playtimes > 6) playtimes -= 6;
continue;
}
if(playtimes > 6) playtimes -= 6;
vector<pii>tmp;
tmp.push_back({x,y});
auto nn = pos(dir,x,y);
// cout << nn.first << " " << nn.second << endl;
while(1)
{
auto [x,y] = tmp.back();
auto [dx,dy] = pos(dir,x,y);
int nexx = x + dx; int nexy = y + dy;
// cout << nexx << " " << nexy << endl;
if(nexx <= 0 || nexx > 17 || nexy <= 0 || nexy > len[nexx])
break;
tmp.push_back({nexx,nexy});
}
int tmplen = 0;
// for(auto x:tmp)
// {
// cout << x.first << " " << x.second << endl;
// }
// cout << endl;
for(int i = 1; i < tmp.size(); i++)
{
auto [nx,ny] = tmp[i];
if(mp[nx][ny] != 0)
continue;
if(obe(x,y) == 0)
continue;
// cout << nx << " " << ny << endl;
if(i == 1)
{
tmplen = 1;
}
else
{
vector<int>cnt;
for(int j = 1; j < i; j++)
{
auto [df1,df2] = tmp[j];
if(mp[df1][df2] == 0)
cnt.push_back(0);
else
cnt.push_back(1);
}
int flag = 0;
for(auto jlc:cnt)
if(jlc != 0) flag = 1;
// for(auto jlc:cnt)
// cout << jlc;
// cout << endl;
if(check(cnt) == 1 && flag == 1)
tmplen = i;
}
}
// cout << tmplen << endl;
if(tmplen != 0)
{
auto [df1,df2] = tmp[tmplen];
// cout << x << " " << y << " ### " << df1 << " " << df2 << endl;
// cout << mp[x][y] << " " << mp[df1][df2] << endl;
swap(mp[x][y],mp[df1][df2]);
}
}
vector<node>a[7];
for(int i = 1; i <= 6; i++)
{
for(int j = 1; j <= 17; j++)
{
int tmp = 0;
for(int k = 1; k <= 17; k++)
{
if(mp[j][k] == i)
{
a[i].push_back({j,k});
}
}
}
}
for(int i = 1; i <= 6; i++)
{
sort(a[i].begin(),a[i].end(),cmp);
}
for(int i = 1; i <= 6; i++)
{
for(auto t:a[i])
{
cout << t.x << " " << t.y << " ";
}
cout << endl;
}
}
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t = 1;
// cin>>t;
while(t--)
solve();
}
//cout << fixed << setprecision(5) << num << endl;
// priority_queue<int,vector<int>,less<int>>q;
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3820kb
input:
12 1 1 LL 16 1 UL 10 1 R 5 11 L 11 10 L 7 1 LR 2 2 LR 13 5 UL 12 2 R 5 12 L 11 11 L 6 1 LR
output:
2 1 3 1 3 2 3 3 4 1 4 2 4 3 4 4 5 5 6 9 12 4 14 1 14 2 14 3 14 4 15 1 15 2 15 3 16 2 17 1 10 2 11 1 11 2 12 1 12 3 12 5 13 1 13 2 13 3 13 4 5 7 5 9 5 10 5 13 6 10 6 11 6 12 7 10 7 11 8 10 10 10 11 7 11 9 12 10 12 11 12 12 13 10 13 11 13 12 13 13 5 1 5 2 5 3 5 4 6 2 6 3 7 1 7 2 8 1 11 3
result:
ok 6 lines
Test #2:
score: -100
Wrong Answer
time: 54ms
memory: 3632kb
input:
39 4 1 LR 14 1 UR 13 4 R 6 12 L 13 10 UL 6 2 R 3 1 LL 16 1 UR 13 1 R 6 9 UL 12 12 L 6 4 L 2 1 LL 13 6 R 13 8 UR 6 11 R 10 10 LL 5 2 R 9 1 R 16 2 LL 10 1 UL 5 13 LL 13 13 UL 5 5 R 3 2 UL 17 1 UR 11 8 UL 8 10 LL 13 12 L 6 2 LR 4 2 LL 15 1 LR 11 1 UR 7 11 UL 13 10 UR 8 1 LR 4 4 LR 13 9 UL 13 3 R 39 4 1...
output:
1 1 2 1 2 2 3 1 3 3 4 3 5 6 8 9 9 2 10 2 11 7 12 8 13 10 14 2 14 3 14 4 15 2 15 3 16 1 16 2 9 1 10 1 10 7 11 2 12 1 12 2 12 3 13 2 13 4 13 5 5 9 5 10 5 11 5 12 6 10 6 11 6 12 7 10 9 9 10 9 7 9 10 10 11 10 11 11 12 7 12 9 12 10 12 11 13 1 13 11 5 1 5 3 5 4 5 7 6 1 6 3 7 1 7 2 10 3 11 3 2 1 2 2 ...
result:
wrong answer 2nd lines differ - expected: '11 7 12 8 13 7 14 2 14 3 14 4 15 2 15 3 16 1 16 2', found: '11 7 12 8 13 10 14 2 14 3 14 4 15 2 15 3 16 1 16 2 '