QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#867631#2932. Checker SlideLaVuna47#AC ✓272ms16128kbC++203.0kb2025-01-23 20:42:102025-01-23 20:42:10

Judging History

你现在查看的是最新测评结果

  • [2025-01-23 20:42:10]
  • 评测
  • 测评结果:AC
  • 用时:272ms
  • 内存:16128kb
  • [2025-01-23 20:42:10]
  • 提交

answer

//A tree without skin will surely die.
//A man without face is invincible.
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(S) ((int)S.size())
#define FOR(i, st_, n) for(int i = st_; i < n; ++i)
#define RFOR(i, n, end_) for(int i = (n)-1; i >= end_; --i)
#define x first
#define y second
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef unsigned long long ull;
typedef long double LD;
typedef pair<ull, ull> pull;
using namespace __gnu_pbds;
typedef tree<ll, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
using namespace std;
#ifdef ONPC
mt19937 rnd(228);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif



struct Move
{
	int x1, y1;
	int x2, y2;
};

map<vector<pii>, int> cost;
map<vector<pii>, pair<vector<pii>, Move>> pr;


int solve()
{
	vector<pii> st(4);
	vector<pii> end(4);
	FOR(i,0,4)if(!(cin>>st[i].x>>st[i].y))return 1;
	FOR(i,0,4)cin>>end[i].x>>end[i].y;
	
	sort(all(st));
	sort(all(end));
    queue<pair<int,vector<pii>>> Q;
    Q.push({0,st});
    cost[st]=0;
    vector<pii> D={ {-1,0}, {1, 0}, {0, 1}, {0,-1}};
    while(!Q.empty())
    {
		auto [d, vec]=Q.front();
		Q.pop();
		if(vec==end)
			break;
		for(const auto& [X,Y]: vec)
		{
			vector<pii> restt;
			for(auto [xx,yy]: vec)
			{
				if(!(xx==X && yy==Y))restt.pb({xx,yy});
			}
			assert(sz(restt)==3);
			for(const auto& [dx, dy]: D)
			{
				auto rest=restt;
				
				auto x=X,y=Y;
				while(x+dx >= 0 && x+dx < 6 && y+dy>=0 && y+dy < 6)
				{
					bool tobreak=false;
					for(auto [xx,yy]:restt)
					{
						if(xx==x+dx && yy==y+dy)
						{
							tobreak=true;
							break;
						}
					}
					if(tobreak)break;
					x+=dx,y+=dy;
				}
				rest.pb({x,y});
				sort(all(rest));
				auto it=cost.find(rest);
				assert(sz(rest)==4);
				assert(sz(rest) == sz(set<pii>(all(rest))));
				if(it==cost.end())
				{
					cost[rest]=d+1;
					Q.push({d+1, rest});
					pr[rest]={vec, {X,Y,x,y}};
				}
			}
		}
	}

	vector<Move> moves;
	
	while(end != st)
	{
		auto [par, move]=pr[end];
		moves.pb(move);
		end=par;
	}
	reverse(all(moves));
	cout<<sz(moves)<<'\n';
	for(auto[x1,y1,x2,y2]: moves)
	{
		cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<'\n';
	}
	return 0;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int TET = 1e9;
    //cin >> TET;
    for (int i = 1; i <= TET; i++)
    {
        if (solve())
        {
            break;
        }
#ifdef ONPC
        cout << "__________________________" << endl;
#endif
    }
#ifdef ONPC
    cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
#endif
}

詳細信息

Test #1:

score: 100
Accepted
time: 93ms
memory: 9856kb

input:

5 5 5 0 0 5 0 0
2 2 2 1 1 2 1 1

output:

12
0 5 4 5
5 0 1 0
0 0 0 5
4 5 1 5
5 5 2 5
1 5 1 1
0 5 1 5
1 5 1 2
1 1 5 1
1 0 1 1
5 1 2 1
2 5 2 2

result:

ok correct plan

Test #2:

score: 0
Accepted
time: 258ms
memory: 15232kb

input:

3 2 2 1 1 0 0 3
4 3 3 5 1 3 0 4

output:

18
1 0 5 0
2 1 2 5
5 0 5 5
5 5 3 5
2 5 0 5
0 5 0 4
0 3 5 3
3 5 3 3
3 2 0 2
0 2 0 3
0 3 2 3
3 3 4 3
5 3 5 0
5 0 0 0
0 0 0 3
0 3 1 3
2 3 3 3
3 3 3 5

result:

ok correct plan

Test #3:

score: 0
Accepted
time: 7ms
memory: 4736kb

input:

5 5 3 4 2 0 0 2
3 4 3 0 0 2 0 1

output:

4
5 5 5 0
5 0 3 0
2 0 0 0
0 0 0 1

result:

ok correct plan

Test #4:

score: 0
Accepted
time: 32ms
memory: 6528kb

input:

3 5 2 1 1 5 0 3
2 2 1 3 1 2 0 1

output:

6
3 5 2 5
2 5 2 2
2 1 0 1
0 3 0 2
0 2 1 2
1 5 1 3

result:

ok correct plan

Test #5:

score: 0
Accepted
time: 78ms
memory: 9344kb

input:

2 2 1 5 0 3 0 1
2 2 1 4 0 3 0 1

output:

8
0 3 0 2
0 2 1 2
1 2 1 4
1 5 0 5
0 5 0 2
0 2 1 2
1 2 1 3
1 3 0 3

result:

ok correct plan

Test #6:

score: 0
Accepted
time: 15ms
memory: 4864kb

input:

5 0 4 5 3 0 1 0
4 4 4 0 3 5 1 0

output:

6
5 0 4 0
4 0 4 4
4 5 5 5
5 5 5 0
5 0 4 0
3 0 3 5

result:

ok correct plan

Test #7:

score: 0
Accepted
time: 260ms
memory: 15616kb

input:

5 3 4 3 1 4 1 2
3 4 3 2 2 2 0 1

output:

18
1 2 1 3
1 3 3 3
1 4 0 4
4 3 4 0
5 3 4 3
4 3 4 1
4 0 0 0
0 4 0 1
0 1 3 1
0 0 0 5
4 1 4 5
0 5 3 5
3 5 3 4
3 3 3 2
3 1 0 1
4 5 0 5
0 5 0 2
0 2 2 2

result:

ok correct plan

Test #8:

score: 0
Accepted
time: 272ms
memory: 16128kb

input:

1 5 1 4 1 3 1 0
5 3 5 2 3 4 3 1

output:

20
1 0 5 0
1 3 5 3
1 5 5 5
5 3 5 4
5 4 2 4
5 0 5 4
5 4 3 4
2 4 2 0
1 4 2 4
2 4 2 1
2 0 5 0
5 5 5 1
5 0 0 0
0 0 0 5
0 5 5 5
5 5 5 2
5 1 3 1
2 1 2 5
2 5 5 5
5 5 5 3

result:

ok correct plan

Test #9:

score: 0
Accepted
time: 264ms
memory: 15616kb

input:

3 4 3 3 3 1 2 3
5 1 1 4 1 1 0 2

output:

16
2 3 0 3
0 3 0 5
3 1 0 1
3 3 0 3
0 3 0 4
0 5 5 5
3 4 1 4
0 4 0 2
5 5 5 0
0 2 5 2
5 0 5 1
5 1 1 1
0 1 0 0
0 0 5 0
5 0 5 1
5 2 0 2

result:

ok correct plan

Test #10:

score: 0
Accepted
time: 16ms
memory: 5248kb

input:

3 2 2 0 0 2 0 1
2 1 1 0 0 2 0 1

output:

5
0 2 2 2
2 0 2 1
2 2 0 2
3 2 1 2
1 2 1 0

result:

ok correct plan

Test #11:

score: 0
Accepted
time: 49ms
memory: 7936kb

input:

3 2 3 1 2 3 0 4
3 2 1 2 0 3 0 2

output:

6
3 1 0 1
0 4 0 2
0 2 2 2
2 3 0 3
0 1 0 2
2 2 1 2

result:

ok correct plan

Test #12:

score: 0
Accepted
time: 33ms
memory: 7040kb

input:

3 1 2 3 1 2 0 2
5 0 2 1 1 2 1 1

output:

6
0 2 0 0
2 3 2 0
0 0 1 0
1 0 1 1
2 0 5 0
3 1 2 1

result:

ok correct plan

Test #13:

score: 0
Accepted
time: 77ms
memory: 9856kb

input:

3 3 3 1 2 3 0 4
2 0 1 5 1 0 0 3

output:

7
0 4 0 0
3 1 3 0
3 0 1 0
1 0 1 5
2 3 2 0
0 0 1 0
3 3 0 3

result:

ok correct plan

Test #14:

score: 0
Accepted
time: 260ms
memory: 15360kb

input:

3 1 2 2 1 3 0 1
4 4 3 2 2 3 0 0

output:

18
0 1 2 1
1 3 1 5
3 1 3 5
1 5 2 5
2 2 2 4
2 1 2 3
2 4 5 4
2 5 2 4
2 4 4 4
3 5 3 0
5 4 5 0
5 0 4 0
4 0 4 3
4 3 3 3
3 0 3 2
3 3 5 3
5 3 5 0
5 0 0 0

result:

ok correct plan

Test #15:

score: 0
Accepted
time: 56ms
memory: 8192kb

input:

5 3 3 1 2 5 2 4
3 4 0 4 0 2 0 1

output:

7
2 5 5 5
3 1 0 1
5 3 5 4
5 4 3 4
5 5 0 5
0 5 0 2
2 4 0 4

result:

ok correct plan