oj.uz

Submission #939596

# Submission time Handle Problem Language Result Execution time Memory
939596 2024-03-06T14:51:18 Z pcc Stray Cat (JOI20_stray) C++14
15 / 100
 35 ms 17344 KB 
#include "Anthony.h"
#include <vector>
#include <bits/stdc++.h>


namespace ANTHONY{

#define pii pair<int,int>
#define fs first
#define sc second
	using namespace std;
	const int mxn = 2e4+10;
	int N,M;
	vector<pii> paths[mxn];
	vector<pii> edges;

	namespace S1{
		queue<int> q;
		int dist[mxn];
		void BFS(){
			memset(dist,-1,sizeof(dist));
			dist[0] = 0;
			q.push(0);
			while(!q.empty()){
				auto now = q.front();
				q.pop();
				for(auto nxt:paths[now]){
					if(dist[nxt.fs] == -1)dist[nxt.fs] = dist[now]+1,q.push(nxt.fs);
				}
			}
			return;
		}
		vector<int> GO(){
			//cout<<"CASE 1"<<endl;
			vector<int> ans(M,0);
			BFS();
			for(int i = 0;i<M;i++){
				auto [a,b] = edges[i];
				if(dist[a]>dist[b])swap(a,b);
				if(dist[a]==dist[b])ans[i] = (dist[a]+1)%3;
				else ans[i] = dist[b]%3;
				//cout<<a<<' '<<b<<" "<<ans[i]<<endl;
			}
			//for(int i = 0;i<N;i++)cout<<dist[i]<<' ';cout<<endl;
			//cout<<ans.size()<<endl;
			//for(auto &i:ans)cout<<i;cout<<endl;
			return ans;
		}
	}

	namespace S2{
		string bin = "100110";//11:0,12:1
		vector<int> ans;
		void dfs(int now,int fa,int pt){
			for(auto nxt:paths[now]){
				if(nxt.fs == fa)continue;
				if(paths[nxt.fs].size() != 2){
					if(pt>10){
						ans[nxt.sc] = (pt==11?0:1);
						dfs(nxt.fs,now,(pt==11?12:11));
					}
					else{
						if(bin[pt]=='0'){
							ans[nxt.sc] = 0;
							dfs(nxt.fs,now,12);
						}
						else{
							ans[nxt.sc] = 1;
							dfs(nxt.fs,now,11);
						}
					}
				}
				else{
					if(pt==11){
						ans[nxt.sc] = 0;
						dfs(nxt.fs,now,0);
					}
					else if(pt == 12){
						ans[nxt.sc] = 1;
						dfs(nxt.fs,now,1);
					}
					else{
						ans[nxt.sc] = bin[pt]-'0';
						dfs(nxt.fs,now,(pt+1)%bin.size());
					}
				}
			}
			return;
		}
		vector<int> GO(){
			ans.resize(M);
			dfs(0,0,11);
			for(int i = 0;i<M;i++){
				cout<<edges[i].fs<<' '<<edges[i].sc<<" "<<ans[i]<<endl;
			}
			return ans;
		}
	}

	vector<int> SOLVE(int n,int m,int a,int b,vector<int> va,vector<int> vb){
		N = n,M = m;
		for(int i = 0;i<m;i++){
			edges.push_back({va[i],vb[i]});
			paths[va[i]].push_back({vb[i],i});
			paths[vb[i]].push_back({va[i],i});
		}
		if(a>=3)return S1::GO();
		else return S2::GO();
	}
}  // namespace

std::vector<int> Mark(int N, int M, int A, int B,
                      std::vector<int> U, std::vector<int> V) {
  return ANTHONY::SOLVE(N,M,A,B,U,V);
}

#include "Catherine.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fs first
#define sc second

namespace NEKO{

int task;
vector<int> route;
int turn;

}  // namespace

void Init(int A, int B) {
	NEKO::task = (A<=2);
	NEKO::turn = 3;
	return;
}

namespace S1{
	int GO(vector<int> v){
		int sum = 0;
		for(auto &i:v)sum += (i?1:0);
		if(sum == 1)return max_element(v.begin(),v.end())-v.begin();
		int s = 0;
		for(int i = 0;i<3;i++){
			if(v[i])s ^= i;
		}
		switch(s){
			case 1:
				return 0;
			case 2:
				return 2;
			case 3:
				return 1;
		}
		assert(false);
		return -1;
	}
}

namespace S2{
	int pre = -1;
	int nt = -1;
	int C0(vector<int> v){
		cout<<"C0"<<endl;
		int s = 0;
		for(auto &i:v)s += (i!=0);
		if(s == 1){
			return (pre = max_element(v.begin(),v.end())-v.begin());
		}
		else if(s == 0)return -1;
		else return (pre ^= 1);
	}
	int C1(vector<int> v){
		cout<<"C1"<<endl;
		nt = 0;
		for(int i = 0;i<2;i++){
			if(v[i] == 1)return (pre = i);
		}
		assert(false);
	}
	int C2(vector<int> v){
		cout<<"C2"<<endl;
		int s = (v[0]?0:1);
		NEKO::turn--;
		if(pre == -1){
			NEKO::route.push_back((v[0]?0:1));
			if(v[1])s = 1;
			else s = 0;
			NEKO::route.push_back(s);
			return (pre = s);
		}
		else if(NEKO::turn>=0){
			NEKO::route.push_back(s);
			return (pre = s);
		}
		else if(NEKO::turn == -1){
			NEKO::route.push_back(s);
			return -1;
		}
		else if(NEKO::turn >= -3){
			return (pre = s);
		}
		string ss;
		for(auto &i:NEKO::route){
			ss += '0'+i;
		}
		cout<<ss<<endl;
		string t = "100110100110100110";
		bool flag = false;
		for(int i = 0;i+ss.size()<=t.size();i++){
			if(t.substr(i,ss.size()) == ss)flag = true;
		}
		nt = 0;
		if(flag)return s;
		else return -1;
	}
	int GO(vector<int> v){
		int re = -2;
		if(!nt)re = C0(v);
		int s = 0;
		for(auto &i:v)s +=i;
		if(re == -2&&s + (pre>=0) != 2){
			if(pre == -1){
				nt = 0;
				re = C0(v);
			}
			else{
				v[pre]++;
				nt = 0;
				if(v[pre] == 1)re = pre;
				else re = (pre ^= 1);
			}
		}
		if(re == -2)re = C2(v);
		for(auto &i:v)cout<<i<<' ';cout<<s<<","<<pre<<":"<<re<<endl;
		return re;
	}
}

int Move(std::vector<int> y) {
	if(NEKO::task)return S2::GO(y);
	else return S1::GO(y);
}

Compilation message

Anthony.cpp: In function 'std::vector<int> ANTHONY::S1::GO()':
Anthony.cpp:38:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |     auto [a,b] = edges[i];
      |          ^

Catherine.cpp: In function 'int S2::GO(std::vector<int>)':
Catherine.cpp:120:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  120 |   for(auto &i:v)cout<<i<<' ';cout<<s<<","<<pre<<":"<<re<<endl;
      |   ^~~
Catherine.cpp:120:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  120 |   for(auto &i:v)cout<<i<<' ';cout<<s<<","<<pre<<":"<<re<<endl;
      |                              ^~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16356 KB Output is correct
2 Correct 1 ms 1312 KB Output is correct
3 Correct 23 ms 15592 KB Output is correct
4 Correct 33 ms 17340 KB Output is correct
5 Correct 35 ms 17344 KB Output is correct
6 Correct 28 ms 16468 KB Output is correct
7 Correct 26 ms 16220 KB Output is correct
8 Correct 31 ms 16856 KB Output is correct
9 Correct 32 ms 16684 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16356 KB Output is correct
2 Correct 1 ms 1312 KB Output is correct
3 Correct 23 ms 15592 KB Output is correct
4 Correct 33 ms 17340 KB Output is correct
5 Correct 35 ms 17344 KB Output is correct
6 Correct 28 ms 16468 KB Output is correct
7 Correct 26 ms 16220 KB Output is correct
8 Correct 31 ms 16856 KB Output is correct
9 Correct 32 ms 16684 KB Output is correct
10 Correct 26 ms 14296 KB Output is correct
11 Correct 28 ms 14116 KB Output is correct
12 Correct 26 ms 14436 KB Output is correct
13 Correct 25 ms 14280 KB Output is correct
14 Correct 26 ms 14524 KB Output is correct
15 Correct 28 ms 14796 KB Output is correct
16 Correct 34 ms 16844 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 13684 KB Output is correct
2 Correct 1 ms 1312 KB Output is correct
3 Correct 22 ms 13548 KB Output is correct
4 Correct 32 ms 15260 KB Output is correct
5 Correct 34 ms 15116 KB Output is correct
6 Correct 28 ms 13868 KB Output is correct
7 Correct 26 ms 13788 KB Output is correct
8 Correct 32 ms 14508 KB Output is correct
9 Correct 31 ms 14584 KB Output is correct
10 Correct 28 ms 14564 KB Output is correct
11 Correct 27 ms 14296 KB Output is correct
12 Correct 27 ms 14536 KB Output is correct
13 Correct 33 ms 14296 KB Output is correct
14 Correct 31 ms 14552 KB Output is correct
15 Correct 30 ms 14548 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 13684 KB Output is correct
2 Correct 1 ms 1312 KB Output is correct
3 Correct 22 ms 13548 KB Output is correct
4 Correct 32 ms 15260 KB Output is correct
5 Correct 34 ms 15116 KB Output is correct
6 Correct 28 ms 13868 KB Output is correct
7 Correct 26 ms 13788 KB Output is correct
8 Correct 32 ms 14508 KB Output is correct
9 Correct 31 ms 14584 KB Output is correct
10 Correct 28 ms 14564 KB Output is correct
11 Correct 27 ms 14296 KB Output is correct
12 Correct 27 ms 14536 KB Output is correct
13 Correct 33 ms 14296 KB Output is correct
14 Correct 31 ms 14552 KB Output is correct
15 Correct 30 ms 14548 KB Output is correct
16 Correct 25 ms 12392 KB Output is correct
17 Correct 23 ms 12332 KB Output is correct
18 Correct 26 ms 12292 KB Output is correct
19 Correct 24 ms 12244 KB Output is correct
20 Correct 27 ms 13000 KB Output is correct
21 Correct 26 ms 12748 KB Output is correct
22 Correct 28 ms 14816 KB Output is correct
23 Correct 27 ms 12432 KB Output is correct
24 Correct 25 ms 12396 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1312 KB Program didn't exit properly, or you printed something to stdout.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 4464 KB Program didn't exit properly, or you printed something to stdout.
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 4304 KB Program didn't exit properly, or you printed something to stdout.
2 Halted 0 ms 0 KB -