QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#487259#5339. Mixing ColoursPetroTarnavskyi#WA 1721ms176380kbC++201.9kb2024-07-22 19:22:322024-07-22 19:22:33

Judging History

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

  • [2024-07-22 19:22:33]
  • 评测
  • 测评结果:WA
  • 用时:1721ms
  • 内存:176380kb
  • [2024-07-22 19:22:32]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

map<string, int> id;
map<int, string> rid;
int addStr(string a)
{
	if(!id.count(a))
	{
		id[a] = SZ(id);
		rid[id[a]] = a;
	}
	return id[a];
}

const int INF = 1e9;
const int N = 1 << 9;
const int R = 104;



vector<PII> rules[3 * R];

db dpT[N][N][3 * R];

void solve()
{
	int n;
	cin >> n;
	
	FOR(i, 0, n + 1)
		FOR(j, 0, n + 1)
			fill(dpT[i][j], dpT[i][j] + 3 * R, -INF);
	
	FOR(i, 0, n)
	{
		string s;
		while(cin >> s)
		{
			if(s == "END")
				break;
			
			int col = addStr(s);
			db prob;
			cin >> prob;
			prob = log(prob);
			
			dpT[i][i + 1][col] = prob;
		}
	}
	int sz = SZ(id);
	RFOR(l, n, 0)
	{
		FOR(r, l + 2, n + 1)
		{
			FOR(c, 0, sz)
			{
				FOR(m, l + 1, r)
				{
					db sum = 0;
					for(auto rule : rules[c])
						sum += exp(dpT[l][m][rule.F] + dpT[m][r][rule.S]);
						
					dpT[l][r][c] = max(dpT[l][r][c], log(sum));
				}				
			}
		}
	}
	int ans = -1;
	FOR(c, 0, sz)
	{
		if(dpT[0][n][c] == -INF)
			continue;
			
		if(ans == -1 || dpT[0][n][c] > dpT[0][n][ans])
			ans = c;
	}
	if(ans == -1)
		cout << "GAMEOVER\n";
	else
		cout << rid[ans] << "\n";
}


int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int r;	
	cin >> r;
	FOR(i, 0, r)
	{
		string a, b, c;
		cin >> a >> b >> c;
		
		int A = addStr(a);
		int B = addStr(b);
		int C = addStr(c);
		
		rules[C].PB({A, B});
		rules[C].PB({B, A});
	}
	
	int q;
	cin >> q;
	while(q--)
	{
		solve();
	}
	
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 10244kb

input:

7
Blue Yellow Green
Yellow Red Orange
Green Red Yellow
White Red Pink
Pink Black Red
Orange Red Red
Yellow Orange Yellow
3
2
Red 0.7 Orange 0.3 END
Yellow 1.0 END
4
Blue 0.6 Green 0.4 END
Red 0.2 Orange 0.6 Yellow 0.2 END
White 0.9 Yellow 0.1 END
Red 0.5 Black 0.5 END
2
Blue 1.0 END
Orange 1.0 END

output:

Orange
Yellow
GAMEOVER

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 1721ms
memory: 176380kb

input:

100
Red Corn Blue
Red Sand Blond
Red Blush Lion
Tan Gray Drab
Tan Kobe Lava
Tan Amber Peru
Tan Blush Ecru
Ube Pink Puce
Ube Camel Aqua
Jet Ceil Onyx
Jet Rose Cyan
Blue Fawn Flax
Blue Peru Rust
Blue Snow Ceil
Blue Camel Ube
Aqua Mint Rose
Aqua Onyx Beige
Aqua Sand Jet
Aqua Snow Beige
Aqua Soap Lion
B...

output:

Blue
Jet
Camel
Iris
GAMEOVER

result:

wrong answer 1st lines differ - expected: 'Lion', found: 'Blue'