oj.uz

답안 #1042664

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1042664 2024-08-03T09:18:04 Z Unforgettablepl Tricolor Lights (JOI24_tricolor) C++17
0 / 100
 65 ms 28868 KB 
#include "Anna.h"
#include <bits/stdc++.h>
using namespace std;

namespace {

string calc(vector<int> arr,string S){
	int N = S.size();
	string res(N,'$');
	for(int i=0;i<N-1;i++){
		if(arr[i])continue;
		{
			vector<bool> present(3);
			if(S[i]=='R')present[0]=true;
			else if(S[i]=='G')present[1]=true;
			else if(S[i]=='B')present[2]=true;
			if(S[i+1]=='R')present[0]=true;
			else if(S[i+1]=='G')present[1]=true;
			else if(S[i+1]=='B')present[2]=true;
			if(!present[0])res[i]=res[i+1]='R';
			else if(!present[1])res[i]=res[i+1]='G';
			else if(!present[2])res[i]=res[i+1]='B';
		}
		for(int j=i-1;j>=0;j--){
			if(arr[j]!=1)break;
			vector<bool> present(3);
			if(S[j]=='R')present[0]=true;
			else if(S[j]=='G')present[1]=true;
			else if(S[j]=='B')present[2]=true;
			if(res[j+1]=='R')present[0]=true;
			else if(res[j+1]=='G')present[1]=true;
			else if(res[j+1]=='B')present[2]=true;
			if(!present[0])res[j]='R';
			else if(!present[1])res[j]='G';
			else if(!present[2])res[j]='B';
		}
		for(int j=i+2;j<N;j++){
			if(arr[j-1]!=1)break;
			vector<bool> present(3);
			if(S[j]=='R')present[0]=true;
			else if(S[j]=='G')present[1]=true;
			else if(S[j]=='B')present[2]=true;
			if(res[j-1]=='R')present[0]=true;
			else if(res[j-1]=='G')present[1]=true;
			else if(res[j-1]=='B')present[2]=true;
			if(!present[0])res[j]='R';
			else if(!present[1])res[j]='G';
			else if(!present[2])res[j]='B';	
		}
	}
	for(int i=0;i<N;i++){
		if(res[i]=='$'){
			if(S[i]=='R')res='B';
			else if(S[i]=='B')res='G';
			else if(S[i]=='G')res='R';
		}
		for(int j=i+1;j<N;j++){
			if(arr[j-1]!=1)break;
			vector<bool> present(3);
			if(S[j]=='R')present[0]=true;
			else if(S[j]=='G')present[1]=true;
			else if(S[j]=='B')present[2]=true;
			if(res[j-1]=='R')present[0]=true;
			else if(res[j-1]=='G')present[1]=true;
			else if(res[j-1]=='B')present[2]=true;
			if(!present[0])res[j]='R';
			else if(!present[1])res[j]='G';
			else if(!present[2])res[j]='B';	
		}
	}
	assert(res.size()==N);
	return res;
}


vector<int> generateDe(int n){
	vector<int> debrujin;
	n--;
	for(int i=1;i<=n;i++)debrujin.emplace_back(1);
	vector<pair<bool,bool>> visited(1<<n);
	function<void(int)> dfs = [&](int x){
		if(!visited[x].first){
			debrujin.emplace_back(0);
			visited[x].first=true;
			dfs((x<<1)&((1<<n)-1));
		}
		if(!visited[x].second){
			debrujin.emplace_back(1);
			visited[x].second=true;
			dfs(((x<<1)&((1<<n)-1))+1);
		}
	};
	dfs(0);
	return debrujin;
}

}

pair<string, int> anna(int N, string S) {
	if(N<=130){
		string res;
		for(int i=0;i<N;i++){
			if(S[i]=='R')res.insert(res.end(),'B');
			else if(S[i]=='B')res.insert(res.end(),'G');
			else if(S[i]=='G')res.insert(res.end(),'R');
		}
		return {res,N};
	}
	auto debrujin = generateDe(18);
	vector<int> res(N+6,2);
	int itr = 0;
	for(int i=1;i<N;i+=3){
		if(debrujin[itr++]==0){
			res[i]=0;
			res[i+1]=1;
		} else {
			res[i-1]=res[i]=res[i+1]=1;
		}
	}
	return {calc(res,S),56};
}
#include "Bruno.h"
#include <bits/stdc++.h>
using namespace std;

namespace {

int N;
int l;

vector<int> generateDe(int n){
	vector<int> debrujin;
	n--;
	for(int i=1;i<=n;i++)debrujin.emplace_back(1);
	vector<pair<bool,bool>> visited(1<<n);
	function<void(int)> dfs = [&](int x){
		if(!visited[x].first){
			debrujin.emplace_back(0);
			visited[x].first=true;
			dfs((x<<1)&((1<<n)-1));
		}
		if(!visited[x].second){
			debrujin.emplace_back(1);
			visited[x].second=true;
			dfs(((x<<1)&((1<<n)-1))+1);
		}
	};
	dfs(0);
	return debrujin;
}

vector<int> debrujin;

}  // namespace

void init(int N, int l) {
	::N = N;
	::l = l;
	debrujin = generateDe(18);
}

int bruno(string u) {
	if(N<=130)return 1;
	vector<int> res(l-1);
	for(int i=0;i<l-1;i++)res[i]=u[i]!=u[i+1];
	bool found = false;
	int offset = 0;
	for(int i=0;i<l-2;i++){
		if(res[i])continue;
		if(res[i+1]==0)offset=i+1%3;
		else offset = i%3;
		found = true;
		break;
	}
	assert(found);
	vector<int> myseq;
	for(int i=offset;i<l-1;i+=3){
		if(myseq.size()==18)break;
		myseq.emplace_back(res[i]);
	}
	assert(myseq.size()==18);
	for(int i=0;i<N;i++){
		bool works = true;
		for(int j=0;j<18;j++){
			if(myseq[j]!=debrujin[i+j]){works=false;break;}
		}
		if(!works)continue;
		return i*3+2-offset;
	}
	assert(false);
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from Anna.cpp:2:
Anna.cpp: In function 'std::string {anonymous}::calc(std::vector<int>, std::string)':
Anna.cpp:71:19: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   71 |  assert(res.size()==N);
      |         ~~~~~~~~~~^~~

Subtask #1
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 16000 KB Output is correct
2 Correct 42 ms 15916 KB Output is correct
3 Correct 53 ms 15964 KB Output is correct
4 Correct 47 ms 15848 KB Output is correct
5 Correct 65 ms 15836 KB Output is correct
6 Correct 45 ms 15856 KB Output is correct
7 Runtime error 28 ms 28868 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #2
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 16000 KB Output is correct
2 Correct 42 ms 15916 KB Output is correct
3 Correct 53 ms 15964 KB Output is correct
4 Correct 47 ms 15848 KB Output is correct
5 Correct 65 ms 15836 KB Output is correct
6 Correct 45 ms 15856 KB Output is correct
7 Runtime error 28 ms 28868 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 16000 KB Output is correct
2 Correct 42 ms 15916 KB Output is correct
3 Correct 53 ms 15964 KB Output is correct
4 Correct 47 ms 15848 KB Output is correct
5 Correct 65 ms 15836 KB Output is correct
6 Correct 45 ms 15856 KB Output is correct
7 Runtime error 28 ms 28868 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #4
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 16000 KB Output is correct
2 Correct 42 ms 15916 KB Output is correct
3 Correct 53 ms 15964 KB Output is correct
4 Correct 47 ms 15848 KB Output is correct
5 Correct 65 ms 15836 KB Output is correct
6 Correct 45 ms 15856 KB Output is correct
7 Runtime error 28 ms 28868 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #5
0.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 15996 KB Output is correct
2 Correct 53 ms 15928 KB Output is correct
3 Correct 43 ms 15992 KB Output is correct
4 Correct 55 ms 15948 KB Output is correct
5 Partially correct 46 ms 16052 KB Partially correct
6 Partially correct 43 ms 16060 KB Partially correct
7 Runtime error 29 ms 28648 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -