QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#72913#4583. Concerto de PandemicpauloamedWA 427ms25056kbC++175.3kb2023-01-20 08:24:192023-01-20 08:24:22

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-20 08:24:22]
  • 评测
  • 测评结果:WA
  • 用时:427ms
  • 内存:25056kb
  • [2023-01-20 08:24:19]
  • 提交

answer

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

#define int long long

const int MAXN = 200010;

vector<int> fans;
vector<pair<int,int>> v[MAXN];

vector<int> pos;

namespace cactus{
	vector<vector<int>> get_cycles(vector<int> to){
		int n = to.size();

		queue<int> q;

		vector<int> indeg(n, 0);
		for(auto x : to) indeg[x]++;
		for(int i = 0; i < n; ++i) if(indeg[i] == 0)
			q.push(i);

		while(q.size()){
			int x = q.front(); q.pop();
			if(--indeg[to[x]] == 0)
				q.push(to[x]);
		}

		vector<vector<int>> cycles;
		for(int i = 0; i < n; ++i) if(indeg[i] == 1){
			vector<int> cycle;
			int x = to[i];
			while(true){
				cycle.push_back(x);
				indeg[x] = 0;
				if(x == i) break;
				x = to[x];
			}
			cycles.push_back(cycle);
		}
		return cycles;
	}
}

namespace circular_arc{
struct Point{
	int x, arc_id;
	bool is_l;
};

vector<int> get_next(vector<Point> &pts, const vector<pair<int,int>> &v){
	int n = v.size();

	vector<pair<int,int>> time_vis(n, {-1, -1});
	vector<int> next(n, -1);
	vector<bool> is_open(n);
	queue<int> closed;

	for(int i = 0; i < 3 * pts.size(); ++i){
		int j = i % pts.size();
		auto [p, arc_id, is_l] = pts[j];

		if(is_l){ // is L
			time_vis[arc_id].first = i;
			is_open[arc_id] = 1;
		}else if(is_open[arc_id]){ // is R and already openned
			time_vis[arc_id].second = i;
			is_open[arc_id] = 0;
			while(closed.size()){
				if(closed.front() != arc_id){
					if(time_vis[arc_id].first < time_vis[closed.front()].second) 
						break;
				}
				next[closed.front()] = arc_id;
				closed.pop();
			}
			if(next[arc_id] == -1)
				closed.push(arc_id);
		}
	}

	return next;
}

int get_min_clique(const vector<pair<int,int>> &v){
	if(v.size() == 0) return 0;
	vector<Point> pts;

	for(int i = 0; i < v.size(); ++i){
		pts.push_back({v[i].first, i, 1});
		pts.push_back({v[i].second, i, 0});
	}

	sort(pts.begin(), pts.end(), [](Point &a, Point &b){
		if(a.x == b.x) return a.is_l > b.is_l;
		else return a.x < b.x;
	});

	auto next = get_next(pts, v);
	auto cycles = cactus::get_cycles(next);

	// for(auto &x : cycles) cout << x.size() << endl;
	// if(cycles.size() == 0){
	// 	cout << "oi" << endl;
	// 	for(auto x : next) cout << x << " ";
	// 	cout << endl; 
	// }

	int max_cycle_size = 0;
	for(auto &c : cycles) 
		max_cycle_size = max(max_cycle_size, (int) c.size());
	// for(auto [l, r] : v) cout << l << " " << r << "\n";
	// cout << "ans: " << max_cycle_size << " " << cycles.size() << endl;
	// cout << "----------------------------\n";
	// cout.flush();

	// assert(cycles.size() == 1);
	return max_cycle_size;
}
}
set<int> fanid;

bool solve(int will_walk, int p){
  // cout << "------------\n";
  // cout << will_walk << "\n";
  int n = pos.size() / 2;

  vector<pair<int,int>> intervs;
  for(int i = 0; i < n; ++i) if(fanid.count(i)){
    int dist = 0;


    int r;
    { // r
      int nxt_pos = pos[i] + will_walk;
      r = upper_bound(pos.begin(), pos.end(), nxt_pos) - pos.begin();
      r--;
      dist += r - i;
      r %= n;
    }

    int l;
    {
      int nxt_pos = pos[i + n] - will_walk;
      l = lower_bound(pos.begin(), pos.end(), nxt_pos) - pos.begin();
      dist += i + n - l;
      l %= n;
    }
    if(dist >= n) continue;

    // cout << l << "(" << i << ")" << r << " : " << dist << "\n";
    // cout << pos[i + n] - will_walk << " " << pos[i] + will_walk  << "\n";
    // cout.flush();
    intervs.push_back({l, r});
  }

  int needed = circular_arc::get_min_clique(intervs);
  // cout << will_walk << ": " << needed << "\n";
  return needed <= p;
}

int32_t main(){
  cin.tie(NULL)->sync_with_stdio(false);
  int n, m, k, p; cin >> n >> m >> k >> p;
  
  vector<int> c(n, 0);
  for(int i = 0; i < m; ++i){
    int j, t; cin >> j >> t; j--;
    c[j] = t;
  }

  for(int i = 0; i < k; ++i){
    int x; cin >> x; x--;
    fans.push_back(x);
  }

  vector<int> good;
  for(int i = 0; i < n; ++i) if(c[i] == 0){
    good.push_back(i);
    // cout << i << " ";
  }
  // cout << "\n";

  if(good.size() == 1){
    cout << 0 << "\n";
    return 0;
  }

  auto id = [&](int x){
    return (int) (lower_bound(good.begin(), good.end(), x) - good.begin());
  };

  for(auto x : fans){
    fanid.insert(id(x));
  }

  for(int i = 0; i < n; ++i) if(c[i] == 0){

    int l = (i - 1 + n) % n;
    int r = (i + 1) % n;
    int cost_l = 1, cost_r = 1;
    
    while(c[l] != 0){
      cost_l += c[l] + 1;
      l = (l - 1 + n) % n;
    }

    while(c[r] != 0){
      cost_r += c[r] + 1;
      r = (r + 1) % n;
    }

    if(l != i) v[id(i)].push_back({id(l), cost_l});
    if(r != i) v[id(i)].push_back({id(r), cost_r});
  }

  int curr_pos = 0;
  for(int i = 0; i < 2 * good.size(); ++i){
    pos.push_back(curr_pos);
    curr_pos += v[i % good.size()][1].second;
  }

  // return 0;
  int tot = pos[good.size()];

  // for(auto x : pos) cout << x << " ";
  // cout << "\n";


  if(solve(0, p)){
    cout << 0 << "\n";
  }else{
    // achar o maior que nao da certo
    int ans = 0;
    int pot = (1LL << 14);
    while(pot){
      int mans = ans + pot;
      if(mans < tot){
        if(!solve(mans, p)) ans = mans;

      }
      pot /= 2;
    }
    cout << ans + 1 << "\n";

  }

}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 8112kb

input:

10 4 3 2
1 2
4 4
6 2
7 5
2 5 8

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 1ms
memory: 8112kb

input:

8 1 3 5
1 5
4 2 7

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 1ms
memory: 8116kb

input:

5 2 2 1
1 14
2 14
3 5

output:

1

result:

ok single line: '1'

Test #4:

score: 0
Accepted
time: 4ms
memory: 8100kb

input:

2 1 1 1
1 200000
2

output:

0

result:

ok single line: '0'

Test #5:

score: -100
Wrong Answer
time: 427ms
memory: 25056kb

input:

190976 113222 55610 23475
51263 120558
10007 171596
46671 108981
117183 169457
18187 84735
149298 124718
79376 129184
28117 76880
109791 87521
114840 59510
38014 178362
41701 11344
27561 192741
173835 54534
71368 76692
122745 95537
152595 158352
43901 162441
98927 105784
22484 96000
19443 113614
370...

output:

32768

result:

wrong answer 1st lines differ - expected: '170531', found: '32768'