QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#136227#5038. CityPetroTarnavskyi#RE 0ms0kbC++173.4kb2023-08-07 17:12:242023-08-07 17:12:25

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-07 17:12:25]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-08-07 17:12:24]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

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

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

const int MAX = 7474;
const int MAX2 = 304;

struct node
{
	int nxt[MAX2];
	int pref[MAX2];
	int cnt;
	
	node()
	{
		cnt = 0;
		FOR (i, 0, MAX2) nxt[i] = -1;
	}
	
} trie[MAX];

int idx = 0;

int roots[14][MAX];
int c[14][MAX];
int prob[14];

void add(VI v, int i, int j)
{
	if (i == SZ(v)) trie[j].cnt++;
	else
	{
		trie[j].cnt++;
		if (trie[j].nxt[v[i]] != -1)
		{
			add(v, i + 1, trie[j].nxt[v[i]]);
		}
		else
		{
			add(v, i + 1, idx++);
		}
	}
}

void add(int cnt, int tot, VI v)
{
	prob[cnt]++;
	c[cnt][tot + 1]++;
	if (roots[cnt][tot] == -1)
	{
		roots[cnt][tot] = idx++;
	}
	add(v, 0, roots[cnt][tot]);
}

vector<PII> parse(string s)
{
	vector<PII> v;
	string t = "";
	FOR (j, 0, SZ(s))
	{
		if (s[j] == ',')
		{	
			int time, wa;
			
			if (t == "-")
			{
				time = 474;
				wa = -1;
			}
			else
			{
				int k = 0;
				while(t[k] != ' ') k++;
				time = stoi(t.substr(0, k));
				wa = stoi(t.substr(k + 1, SZ(t) - (k + 1)));
			}
			t = "";
			v.PB({time, wa});
		}
		else
			t += s[j];
	}
	return v;
}

int get_pos(int cnt, int t, VI& v)
{
	return 0;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	FOR (i, 0, 14) FOR (j, 0, MAX) roots[i][j] = -1;
	
	int n;
	cin >> n;
	VI mn(10, 474);
	int MN = 7474, MX = 0;
	FOR (iter, 0, n - 1)
	{
		string s;
		getline(cin,  s);
		
		vector<PII> v = parse(s);
		int cnt = 0;
		int tot = 0;
		assert(SZ(v) == 10);
		
		FOR (i, 0, SZ(v))
		{
			if (v[i].S != -1)
			{
				cnt++;
				tot += v[i].F + v[i].S * 20;
			}
			mn[i] = min(mn[i], v[i].F);
		}
		if (cnt)
		{
			MN = min(MN, tot);
			MX = max(MX, tot);
		}
		
		sort(ALL(v));
		int j = 9;
		while (j >= 0 && v[j].S == -1)
		{
			v.pop_back();
			j--;
		}
		reverse(ALL(v));
		VI toad;
		FOR (i, 0, j + 1) toad.PB(v[i].F);
		if (j >= 0)
			add(cnt, tot, toad);
	}
	
	FOR (i, 0, MAX)
	{
		trie[i].pref[0] = trie[trie[i].nxt[0]].cnt;
		FOR (j, 1, MAX2) trie[i].pref[j] = trie[i].pref[j - 1] + trie[trie[i].nxt[j]].cnt;
	}
	FOR (i, 0, 14)
	{
		int st = (i ? prob[i - 1] : 0);
		FOR (j, 0, MAX)
		{
			c[i][j] += st;
			st = c[i][j];
		}
	}
	
	string s;
	cin >> s;
	vector<PII> v = parse(s);
	sort(ALL(v));
	
	VI idxes(10);
	iota(ALL(idxes), 0);
	
	int ans = 0;
	do
	{
		int an = 0;
		int p = 0;
		int t = 0;
		int w = 0;
		VI times;
		FOR (i, 0, 10)
		{
			if (v[idxes[i]].S == -1 || v[idxes[i]].F + t > 300) break; // ? +- 1
			
			p++;
			t += v[idxes[i]].F;
			w += v[idxes[i]].S;
			times.PB(t);
			if (t <= mn[idxes[i]]) an += 800; //
		}
		reverse(ALL(times));
		
		if (t + w * 20 <= MN) an += 700;
		if (t + w * 20 >= MX) an += 500;
		
		int pos = get_pos(p, t + w * 20, times);
		
		an += 5000 / pos;
		if (pos <= n / 10) an += 1200;
		else if (pos <= 3 * n / 10) an += 800;
		else if (pos <= 6 * n / 10) an += 400;
		ans = max(ans, an);
	} while (next_permutation(ALL(idxes)));
	
	cout << ans << '\n';
	
	
	
	return 0;
}


详细

Test #1:

score: 0
Runtime Error

input:

1 1

output:


result: