QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#563390#8056. Travel 2N_z_AC ✓179ms27684kbC++145.3kb2024-09-14 10:56:322024-09-14 10:56:32

Judging History

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

  • [2024-09-14 10:56:32]
  • 评测
  • 测评结果:AC
  • 用时:179ms
  • 内存:27684kb
  • [2024-09-14 10:56:32]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
struct time_helper
{
#ifdef LOCAL
	clock_t time_last;
#endif
	time_helper()
	{
#ifdef LOCAL
		time_last=clock();
#endif
	}
	void test()
	{
#ifdef LOCAL
		auto time_now=clock();
		std::cerr<<"time:"<<1.*(time_now-time_last)/CLOCKS_PER_SEC<<";all_time:"<<1.*time_now/CLOCKS_PER_SEC<<std::endl;
		time_last=time_now;
#endif
	}
	~time_helper()
	{
		test();
	}
}time_helper;
#ifdef LOCAL
#include"dbg.h"
#else
#define dbg(...) (__VA_ARGS__)
#endif
// namespace Fread{const int SIZE=1<<16;char buf[SIZE],*S,*T;inline char getchar(){if(S==T){T=(S=buf)+fread(buf,1,SIZE,stdin);if(S==T)return'\n';}return *S++;}}namespace Fwrite{const int SIZE=1<<16;char buf[SIZE],*S=buf,*T=buf+SIZE;inline void flush(){fwrite(buf,1,S-buf,stdout);S=buf;}inline void putchar(char c){*S++=c;if(S==T)flush();}struct NTR{~NTR(){flush();}}ztr;}
// #define getchar Fread::getchar
// #define putchar Fwrite::putchar
#define Setprecision 10
#define between ' '
#define __int128 long long
// template<typename T>struct is_char{static constexpr bool value=(std::is_same<T,char>::value||std::is_same<T,signed char>::value||std::is_same<T,unsigned char>::value);};template<typename T>struct is_integral_ex{static constexpr bool value=(std::is_integral<T>::value||std::is_same<T,__int128>::value)&&!is_char<T>::value;};template<typename T>struct is_floating_point_ex{static constexpr bool value=std::is_floating_point<T>::value||std::is_same<T,__float128>::value;};namespace Fastio{struct Reader{template<typename T>typename std::enable_if_t<std::is_class<T>::value,Reader&>operator>>(T&x){for(auto &y:x)*this>>y;return *this;}template<typename T>typename std::enable_if_t<is_integral_ex<T>::value,Reader&>operator>>(T&x){char c=getchar();short f=1;while(c<'0'||c>'9'){if(c=='-')f*=-1;c=getchar();}x=0;while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x*=f;return *this;}template<typename T>typename std::enable_if_t<is_floating_point_ex<T>::value,Reader&>operator>>(T&x){char c=getchar();short f=1,s=0;x=0;T t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else return x*=f,*this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}template<typename T>typename std::enable_if_t<is_char<T>::value,Reader&>operator>>(T&c){c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();return *this;}Reader&operator>>(char*str){int len=0;char c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')str[len++]=c,c=getchar();str[len]='\0';return*this;}Reader&operator>>(std::string&str){str.clear();char c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')str.push_back(c),c=getchar();return*this;}Reader(){}}cin;const char endl='\n';struct Writer{typedef __int128 mxdouble;template<typename T>typename std::enable_if_t<std::is_class<T>::value,Writer&>operator<<(T x){for(auto &y:x)*this<<y<<between;*this<<'\n';return *this;}template<typename T>typename std::enable_if_t<is_integral_ex<T>::value,Writer&>operator<<(T x){if(x==0)return putchar('0'),*this;if(x<0)putchar('-'),x=-x;static int sta[45];int top=0;while(x)sta[++top]=x%10,x/=10;while(top)putchar(sta[top]+'0'),--top;return*this;}template<typename T>typename std::enable_if_t<is_floating_point_ex<T>::value,Writer&>operator<<(T x){if(x<0)putchar('-'),x=-x;x+=pow(10,-Setprecision)/2;mxdouble _=x;x-=(T)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<Setprecision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}template<typename T>typename std::enable_if_t<is_char<T>::value,Writer&>operator<<(T c){putchar(c);return*this;}Writer&operator<<(char*str){int cur=0;while(str[cur])putchar(str[cur++]);return *this;}Writer&operator<<(const char*str){int cur=0;while(str[cur])putchar(str[cur++]);return*this;}Writer&operator<<(std::string str){int st=0,ed=str.size();while(st<ed)putchar(str[st++]);return*this;}Writer(){}}cout;}
// #define cin Fastio::cin
// #define cout Fastio::cout
// #define endl Fastio::endl
template<class Fun>class y_combinator_result{Fun fun_;public:template<class T>explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}template<class ...Args>decltype(auto) operator()(Args &&...args){return fun_(std::ref(*this), std::forward<Args>(args)...);}};template<class Fun>decltype(auto) y_combinator(Fun &&fun){return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));}

void solve();
main()
{
	int t=1;
	cin>>t;
	while(t--)solve();
}
int d[2501],ok[2501],id[2501][2501];
vector<int>e[2501];
void solve()
{
	int s;
	cin>>s>>d[s];
	auto ask=[&](int u)
	{
		cout<<"> "<<u<<endl;
		int res;
		cin>>res>>d[res];
		return res;
	};
	y_combinator([&](auto dfs,int u)->void
	{
		if(e[u].size()<d[u])
		{
			int v=ask(e[u].size()+1);
			e[u].emplace_back(v);
			id[u][v]=e[u].size();
			dfs(v);
			return;
		}
		ok[u]=1;
		for(int i=0;i<e[u].size();i++)
		{
			if(!ok[e[u][i]])ask(i+1),dfs(e[u][i]),ask(id[e[u][i]][u]);
		}
	})(s);
	cout<<"! ";
	for(int u=1;u<=2500;u++)
	{
		for(auto v:e[u])
		if(u<v)cout<<u<<' '<<v<<' ';
		ok[u]=0;
		e[u].clear();
	}
	cout<<endl;
	string fuck;
	cin>>fuck;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3640kb

input:

2
1 1
2 1
1 1
2 1
1 1
Correct
1 3
2 2
1 3
3 1
1 3
4 2
1 3
2 2
4 2
2 2
4 2
2 2
1 3
3 1
1 3
Correct

output:

> 1
> 1
> 1
> 1
! 1 2 
> 1
> 1
> 2
> 1
> 3
> 1
> 1
> 2
> 2
> 2
> 2
> 1
> 2
> 1
! 1 2 1 3 1 4 2 4 

result:

ok correct! (2 test cases)

Test #2:

score: 0
Accepted
time: 124ms
memory: 3620kb

input:

1000
1 9
2 7
1 9
3 9
1 9
4 9
1 9
5 8
1 9
6 9
1 9
7 7
1 9
8 8
1 9
9 8
1 9
10 6
1 9
2 7
3 9
4 9
3 9
9 8
3 9
2 7
10 6
2 7
6 9
2 7
5 8
8 8
5 8
9 8
5 8
2 7
9 8
2 7
4 9
7 7
4 9
10 6
8 8
10 6
4 9
8 8
9 8
8 8
7 7
8 8
3 9
5 8
3 9
10 6
6 9
10 6
3 9
8 8
6 9
5 8
6 9
8 8
4 9
5 8
7 7
5 8
4 9
2 7
3 9
7 7
3 9
6 9
3...

output:

> 1
> 1
> 2
> 1
> 3
> 1
> 4
> 1
> 5
> 1
> 6
> 1
> 7
> 1
> 8
> 1
> 9
> 1
> 1
> 2
> 2
> 2
> 3
> 2
> 4
> 3
> 2
> 4
> 2
> 5
> 2
> 2
> 3
> 3
> 4
> 6
> 4
> 7
> 3
> 2
> 4
> 3
> 3
> 4
> 5
> 4
> 5
> 5
> 3
> 6
> 5
> 5
> 6
> 5
> 3
> 6
> 7
> 7
> 4
> 6
> 5
> 8
> 6
> 7
> 4
> 8
> 7
> 2
> 8
> 5
> 9
> 6
> 2
> 8
> 7
...

result:

ok correct! (1000 test cases)

Test #3:

score: 0
Accepted
time: 94ms
memory: 5768kb

input:

500
1 19
2 8
1 19
3 7
1 19
4 8
1 19
5 7
1 19
6 7
1 19
7 11
1 19
8 4
1 19
9 7
1 19
10 9
1 19
11 8
1 19
12 7
1 19
13 4
1 19
14 9
1 19
15 8
1 19
16 7
1 19
17 10
1 19
18 7
1 19
19 7
1 19
20 6
1 19
2 8
17 10
2 8
3 7
20 6
3 7
11 8
3 7
4 8
3 7
2 8
14 9
19 7
14 9
17 10
6 7
5 7
7 11
5 7
6 7
17 10
14 9
6 7
11...

output:

> 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
> 1
> 2
> 2
> 3
> 2
> 2
> 3
> 2
> 4
> 2
> 5
> 4
> 2
> 2
> 3
> 3
> 2
> 2
> 2
> 3
> 3
> 4
> 4
> 4
> 3
> 2
> 4
> 2
> 2
> 3
> 5
> 3
> 2
> 4
> ...

result:

ok correct! (500 test cases)

Test #4:

score: 0
Accepted
time: 130ms
memory: 4292kb

input:

100
1 99
2 5
1 99
3 5
1 99
4 10
1 99
5 3
1 99
6 9
1 99
7 6
1 99
8 8
1 99
9 9
1 99
10 5
1 99
11 4
1 99
12 7
1 99
13 6
1 99
14 8
1 99
15 7
1 99
16 7
1 99
17 7
1 99
18 6
1 99
19 10
1 99
20 4
1 99
21 4
1 99
22 5
1 99
23 6
1 99
24 10
1 99
25 4
1 99
26 10
1 99
27 7
1 99
28 6
1 99
29 11
1 99
30 5
1 99
31 7...

output:

> 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
> 3...

result:

ok correct! (100 test cases)

Test #5:

score: 0
Accepted
time: 111ms
memory: 14896kb

input:

10
1 999
2 8
1 999
3 9
1 999
4 8
1 999
5 7
1 999
6 7
1 999
7 4
1 999
8 4
1 999
9 13
1 999
10 11
1 999
11 7
1 999
12 7
1 999
13 5
1 999
14 5
1 999
15 8
1 999
16 9
1 999
17 5
1 999
18 5
1 999
19 8
1 999
20 4
1 999
21 8
1 999
22 8
1 999
23 6
1 999
24 8
1 999
25 2
1 999
26 9
1 999
27 5
1 999
28 6
1 999
...

output:

> 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
> 3...

result:

ok correct! (10 test cases)

Test #6:

score: 0
Accepted
time: 179ms
memory: 13808kb

input:

4
1 999
2 24
1 999
3 20
1 999
4 17
1 999
5 29
1 999
6 21
1 999
7 21
1 999
8 19
1 999
9 21
1 999
10 14
1 999
11 12
1 999
12 17
1 999
13 23
1 999
14 23
1 999
15 16
1 999
16 14
1 999
17 16
1 999
18 15
1 999
19 16
1 999
20 19
1 999
21 16
1 999
22 16
1 999
23 25
1 999
24 23
1 999
25 22
1 999
26 16
1 999
...

output:

> 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
> 3...

result:

ok correct! (4 test cases)

Test #7:

score: 0
Accepted
time: 120ms
memory: 6336kb

input:

4
1 199
2 106
1 199
3 95
1 199
4 102
1 199
5 103
1 199
6 103
1 199
7 110
1 199
8 109
1 199
9 104
1 199
10 98
1 199
11 85
1 199
12 94
1 199
13 86
1 199
14 105
1 199
15 102
1 199
16 96
1 199
17 97
1 199
18 94
1 199
19 112
1 199
20 108
1 199
21 116
1 199
22 109
1 199
23 104
1 199
24 96
1 199
25 92
1 19...

output:

> 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
> 3...

result:

ok correct! (4 test cases)

Test #8:

score: 0
Accepted
time: 65ms
memory: 27684kb

input:

4
1 140
2 140
1 140
3 140
1 140
4 140
1 140
5 140
1 140
6 140
1 140
7 140
1 140
8 140
1 140
9 140
1 140
10 140
1 140
11 140
1 140
12 140
1 140
13 140
1 140
14 140
1 140
15 140
1 140
16 140
1 140
17 140
1 140
18 140
1 140
19 140
1 140
20 140
1 140
21 140
1 140
22 140
1 140
23 140
1 140
24 140
1 140
2...

output:

> 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
> 3...

result:

ok correct! (4 test cases)

Test #9:

score: 0
Accepted
time: 72ms
memory: 27616kb

input:

4
1 2498
2 2
1 2498
3 2
1 2498
4 2
1 2498
5 2
1 2498
6 2
1 2498
7 2
1 2498
8 2
1 2498
9 2
1 2498
10 2
1 2498
11 2
1 2498
12 2
1 2498
13 2
1 2498
14 2
1 2498
15 2
1 2498
16 2
1 2498
17 2
1 2498
18 2
1 2498
19 2
1 2498
20 2
1 2498
21 2
1 2498
22 2
1 2498
23 2
1 2498
24 2
1 2498
25 2
1 2498
26 2
1 2498...

output:

> 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
> 3...

result:

ok correct! (4 test cases)

Extra Test:

score: 0
Extra Test Passed