이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
ID: USACO_template
LANG: C++
PROG: https://oj.uz/problem/view/IOI16_messy
*/
#include <iostream> //cin , cout
#include <fstream> //fin, fout
#include <stdio.h> // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack> // stacks
#include <queue> // queues
#include <map>
#include <string>
#include <string.h>
#include <set>
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi; /// adjlist without weight
typedef vector<pii> vii; /// adjlist with weight
typedef vector<pair<int,pii>> vpip; /// edge with weight
typedef long long ll;
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define sz(x) (int)(x).size()
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; //
const ll INF = 1e18; //
#define MAXV 300007
#define MAXE 100007
const int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1}; /// 4 directions
struct NODE {
int x, y;
int val;
int visited;
bool operator< (NODE b) const { return (x == b.x) ? (y < b.y) : (x < b.x); }
};
struct EDGE {
int from, to;
ll weight;
bool operator<(EDGE other) const { return weight < other.weight; }
};
bool debug=false;
/** use divide and conquer
* we add elements the region of interest is 0. For the first half of this region, we flip 0 -> 1 one at a time
* then we do the check, we binary check whether that elements is in the left or right
*/
#include "messy.h"
vi p;
void dnc_add(int l, int r, int n){
if (l>r) return;
if (l==r) return;
if(debug) cout << "range " << l << " - " << r << endl;
string s = "";
for (int i=0;i<n;i++)
s += (l<=i && i <=r) ? "0" : "1";
int m = (l+r)/2;
for (int i=l;i<=m;i++){ //
s[i] = '1';
add_element(s);
if(debug) cout << " .. add " << s << endl;
s[i] = '0';
}
dnc_add(l, m, n); dnc_add(m+1, r, n);
}
void dnc_check(int l, int r, int n, vi plist){
if(plist.empty()) return;
if(l>r) return;
if(debug) {
cout << "search range " << l << " - " << r << endl << " ";
for(auto i : plist) cout << i << " ";
cout << endl;
}
if (l==r){
p[l] = plist[0]; return;
}
string s(n, '1');
for (auto i : plist) s[i] = '0';
vector<int> L, R;
L.clear(); R.clear();
for (auto i : plist){
s[i] = '1';
if (check_element(s)) L.pb(i);
else R.pb(i);
s[i] = '0';
}
int m = (l+r)/2;
dnc_check(l, m, n, L); dnc_check(m+1, r, n, R);
}
vi restore_permutation(int n, int w, int r) {
p.resize(n);
dnc_add(0, n-1, n);
compile_set();
if(debug) cout << "now find p" << endl;
vi idx;
for (int i=0;i<n;i++) idx.pb(i);
dnc_check(0, n-1, n, idx);
return p;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |