結果

提出番号 2162
提出者 kotamanegi
言語 C++
提出日時 2018-08-16 20:14:37
問題名 (16)Hello World!
結果 CE
点数 0%

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 CE 0% 0ms 0KB

ソースコード

#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
using namespace std;
#define Ma_PI 3.141592653589793
#define eps 0.00000001
#define LONG_INF 3000000000000000000
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define REP(i,n) for(long long i = 0;i < n;++i)    
#define seg_size 524288
#define FAIL 0
#define SUCCESS 1
#include <ctype.h>
typedef string::const_iterator State;
uint32_t xor128(void) { 
  static uint32_t x = 123456789;
  static uint32_t y = 362436069;
  static uint32_t z = 521288629;
  static uint32_t w = 88675123; 
  uint32_t t;
 
  t = x ^ (x << 11);
  x = y; y = z; z = w;
  return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); 
}
vector<string> expression(State &begin);
string s;
vector<vector<string>> inputs;
vector<string> loop(State &begin) {
	vector<vector<string>> ans;
	for (; begin != s.end();) {
		if (*begin == '*') {
			vector<string> tmp = ans[ans.size() - 1];
			ans.pop_back();
			vector<string> a, b;
			a.push_back("split 1 " + to_string(tmp.size() + 2));
			ans.push_back(a);
			ans.push_back(tmp);
			b.push_back("jmp " + to_string(-((int)tmp.size() + 1)));
			ans.push_back(b);
			begin++;
		}
		else if (*begin == '?') {
			vector<string> tmp = ans[ans.size() - 1];
			ans.pop_back();
			vector<string> a;
			a.push_back("split 1 " + to_string(tmp.size() + 1));
			ans.push_back(a);
			ans.push_back(tmp);
			begin++;
		}
		else if (*begin == '+') {
			vector<string> a;
			a.push_back("split 1 " + to_string(-(int)ans[ans.size() - 1].size()));
			ans.push_back(a);
			begin++;
		}
		else if (*begin == '(') {
			begin++;
			vector<string> a = expression(begin);
			ans.push_back(a);
		}
		else if (*begin == ')') {
			break;
		}
		else if (*begin == '|') {
			break;
		}
		else if(*begin == '['){
			string p = "";
			begin++;
			while(*begin != ']'){
				p.push_back(*begin);
				begin++;
			}
			begin++;
			vector<char> going;
			for(int i = 0;i < p.length();++i){
				if(i >= p.length()-2||p[i+1] != '-'){
					going.push_back(p[i]);
				}else{
					for(char q = p[i];q <= p[i+2];++q){
						going.push_back(q);
					}
					i++;
				}
			}
			if(going.empty() == false){
				string pushing = "(";
				pushing.push_back(going[0]);
				for(int i = 1;i < going.size();++i){
					pushing += "|";
					pushing.push_back(going[i]);
				}
				pushing += ")";
				State beginner = pushing.begin();
				beginner++;
				vector<string> a = expression(beginner);
				ans.push_back(a);
			}
		}
		else{
			vector<string> a;
			string b = "char ";
			b.push_back(*begin);
			a.push_back(b);
			ans.push_back(a);
			begin++;
		}
	}
	vector<string> final_ans;
	for (int i = 0; i < ans.size(); ++i) {
		REP(q, ans[i].size()) final_ans.push_back(ans[i][q]);
	}
	return final_ans;
}
vector<string> expression(State &begin) {
	vector<vector<string>> ans;
	ans.push_back(loop(begin));
	for (; begin != s.end();) {
		if (*begin == ')') {
			begin++;
			break;
		}else if(*begin == '('){
			ans.push_back(loop(begin));
			continue;
		}
		begin++;
		vector<string> tmp = loop(begin);
		vector<string> backing = ans[ans.size() - 1];
		ans.pop_back();
		vector<string> a;
		a.push_back("split 1 " + to_string(backing.size() + 2));
		REP(i,backing.size()){
			a.push_back(backing[i]);
		}
		a.push_back("jmp " + to_string(tmp.size() + 1));
		REP(i,tmp.size()){
			a.push_back(tmp[i]);
		}
		ans.push_back(a);
	}
	vector<string> final_ans;
	for (int i = 0; i < ans.size(); ++i) {
		REP(q, ans[i].size()) final_ans.push_back(ans[i][q]);
	}
	return final_ans;
}
vector<string> compiler() {
	cin >> s;
	int check_required = 0;
	if(s[s.length()-1] == '$'){ 
		check_required = 1;
		s.pop_back();
	}
	int first_day = 0;
	if(s[0] == '^'){
		first_day = 1;
		s.erase(s.begin());
	}
	State begin = s.begin();
	vector<string> ans = expression(begin);
	if(check_required == 0){
		ans.push_back("match");
	}else{
		ans.push_back("ifmatch");
	}
	if(first_day == 1){
		ans.insert(ans.begin(),"start");
	}
	return ans;
}
long long ok[10000][10000] = {};
int solve(int start) {
	queue<pair<int,int>> next;
	next.push(make_pair(start,0));
	while(next.empty() == false){
		int SP = next.front().first,PC = next.front().second;
		next.pop();	
		if(ok[SP][PC]){ 
			if(ok[SP][PC] == 2)
				return 2;
			continue;
		}
		if (inputs[PC][0] == "match"){
			return 2;
		}
		if(inputs[PC][0] == "ifmatch"){
			if(SP == s.length()) return 2;
		}
		if (inputs[PC][0] == "char") {
			if (s.length() <= SP) continue;
			if (s[SP] != inputs[PC][1][0]) continue;
			ok[SP][PC] = 1;
			next.push(make_pair(SP+1,PC+1));
		}
		if (inputs[PC][0] == "jmp") {
			ok[SP][PC] = 1;
			next.push(make_pair(SP,PC+stoll(inputs[PC][1])));
		}
		if (inputs[PC][0] == "split") {
			ok[SP][PC] = 1;
			if(xor128() % 2 == 1){		
				next.push(make_pair(SP,PC+stoll(inputs[PC][2])));
				next.push(make_pair(SP,PC+stoll(inputs[PC][1])));
			}else{
				next.push(make_pair(SP,PC+stoll(inputs[PC][1])));
				next.push(make_pair(SP,PC+stoll(inputs[PC][2])));
			}
		}
	}
	return 1;
}

int main(){
	stringstream foooa;
	vector<string> bytecode = compiler();
	for(int i = 0;i < bytecode.size();++i){
		foooa << bytecode[i] << endl;
	}
	int bobo = 0;
	while(bobo < bytecode.size()){
		vector<string> hogea;
		string tmp;
		foooa >> tmp;
		hogea.push_back(tmp);
		bobo++;
		if(hogea[0] == "char"){
			foooa >> tmp;
			hogea.push_back(tmp);
		}
		else if(hogea[0] == "split"){
			foooa >> tmp;
			hogea.push_back(tmp);
			foooa >> tmp;
			hogea.push_back(tmp);
		}
		else if(hogea[0] == "jmp"){
			foooa >> tmp;
			hogea.push_back(tmp);
		}
		inputs.push_back(hogea);
	}
	cin >> s;
	if(inputs[0][0] == "start"){
		inputs.erase(inputs.begin());
		if(solve(0) == 2){
			cout << 0 << endl;
		}else{ 
			cout << -1 << endl;
		}
	}else{
		for(int i = 0;i < s.length();++i){
			if(solve(i) == 2){
				cout << i << endl;
				return 0;
			}
		}
		cout << -1 << endl;
		return 0;
	}
	return 0;
}