QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#235099#7569. Linessalvator_nosterWA 1ms5848kbC++205.1kb2023-11-02 13:58:142023-11-02 13:58:14

Judging History

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

  • [2023-11-02 13:58:14]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5848kb
  • [2023-11-02 13:58:14]
  • 提交

answer

#include <bits/stdc++.h>

template <class T>
inline int qlog(T a) {
	double x = a;
	return ((*(long long*) & x) >> 52 & 2047) - 1023;
}

#define fopen LilyWhite
void fopen(const char *s) {
    static char filename[32];
    sprintf(filename, "%s.in", s);
    freopen(filename, "r", stdin);
    sprintf(filename, "%s.out", s);
    freopen(filename, "w", stdout);
}

typedef unsigned int u32;
typedef long long ll;
typedef unsigned long long u64;

#define Please return
#define AC 0
#define cin Mizuhashi
#define cout Parsee
#define endl '\n'

class Reader{
	private:
	    static const int BUF_SIZE = 1 << 22;
	    char BUF_R[BUF_SIZE], *csy1, *csy2;
	    #ifndef _LOCAL_RUNNING
		    #define GC (csy1 == csy2 && (csy2 = (csy1 = BUF_R) + fread(BUF_R, 1, BUF_SIZE, stdin), csy1 == csy2) ? EOF : *csy1 ++)
		#else
		    char cur;
		    #define GC (cur = getchar())
		#endif
	    #define IL inline
		
    public:
        IL bool eof() {
            #ifndef _LOCAL_RUNNING
                return csy1 == csy2 && (csy2 = (csy1 = BUF_R) + fread(BUF_R, 1, BUF_SIZE, stdin), csy1 == csy2);
            #else
                return cur == EOF;
            #endif
        }
        template <class Ty>
        IL Reader& operator >> (Ty &t) {
            int u = 0;
            char c = GC;
	    	for (t = 0; c < 48 || c > 57; c = GC)
                if (c == EOF) break;
                else if (c == '-') u = 1;
	    	for ( ; c > 47 && c < 58; c = GC) t = t * 10 + (c ^ 48);
	    	t = u ? -t : t; return *this;
        }
    	IL Reader& operator >> (double &t) {
            int tmp, u = 0; char c = GC;
	    	for (tmp = 0; c < 48 || c > 57; c = GC)
                if (c == EOF) break;
                else if (c == '-') u = 1;
	    	for ( ; c > 47 && c < 58; c = GC) tmp = tmp * 10 + (c ^ 48);
	    	t = (tmp = u ? -tmp : tmp);
    	    if (c == '.') {
    	        double x = 1;
    	        for (c = GC; c > 47 && c < 58; c = GC) t += (x /= 10) * (c ^ 48);
    	    }
    	    return *this;
    	}
    	IL Reader& operator >> (char *s) {
			char c = GC;
			for (*s = 0; c < 33; c = GC) if (c == EOF) return *this;
			for ( ; c > 32; c = GC) *s ++ = c;
			*s = 0; return *this;
		}
        IL Reader& operator >> (char &c) {
			for (c = GC; c < 33; c = GC) if (c == EOF) return *this;
            return *this;
        }
}cin;
class Writer{
	private:
	    static const int BUF_SIZE = 1 << 22;
	    char BUF_W[BUF_SIZE], *csy;
	    #define IL inline
		inline void WC(const char c) {
			if (csy - BUF_W == BUF_SIZE) fwrite(BUF_W, 1, BUF_SIZE, stdout), csy = BUF_W;
			*csy ++ = c;
		}
	
	public:
		Writer() : csy(BUF_W) {}
		~ Writer() {fwrite(BUF_W, 1, csy - BUF_W, stdout);}
		IL void flush() {fwrite(BUF_W, 1, csy - BUF_W, stdout); csy = BUF_W;}
		template <class Ty>
		IL Writer& operator << (Ty x) {
		    static int sta[32], top;
			if (x < 0) {
				WC('-');
                do sta[top ++] = - (x % 10); while (x /= 10);
			}else do sta[top ++] = x % 10; while (x /= 10);
			while (top) WC(sta[-- top] ^ 48);
			return *this;
		}
		IL Writer& operator << (const char &c) {WC(c); return *this;}
		IL Writer& operator << (const char *s) {while (*s) WC(*s ++); return *this;}
}cout;

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <pll> vp;

int N;

inline bool check(const pll &a, const pll &b, const pll &c) {
    return (c.second - b.second) * (a.first - c.first) <= (c.second - a.second) * (b.first - c.first);
}

vp Build(const vi &a) {
    vp res(0);
    for (int i = 0; i <= N; i ++) {
        //y = k1x + b1, y = k2x + b2
        //k1x + b1 = k2x + b2
        //x = (b2 - b1) / (k1 - k2)
        pll tmp = {i, a[i]};
        while (res.size() > 1 && check(res[res.size() - 2], res.back(), tmp)) res.pop_back();
        res.push_back(tmp);
    }
    return res;
}

inline pll operator + (const pll &a, const pll &b) {return {a.first + b.first, a.second + b.second};}

vp add(const vp &a, const vp &b) {
    vp res(0);
    for (int i = 0, j = 0; j < b.size(); ) {
        pll tmp = a[i] + b[j];
        while (res.size() > 1 && check(res[res.size() - 2], res.back(), tmp)) res.pop_back();
        res.push_back(tmp);
        if (i + 1 < a.size() && (j + 1 == a.size() || check(a[i] + b[j + 1], a[i + 1] + b[j], res.back()))) i ++;
        else j ++;
    }
    return res;
}

void solve() {
    cin >> N;
    vi a(N + 1), b(N + 1), c(N + 1);
    for (int i = 0; i <= N; i ++) cin >> a[i];
    for (int i = 0; i <= N; i ++) cin >> b[i];
    for (int i = 0; i <= N; i ++) cin >> c[i];
    vp hull = add(Build(a), add(Build(b), Build(c)));
    vi ans(0);
    for (int i = 0, j = 0; i <= N * 3; i ++) {
        if ((j < hull.size()) && i == hull[j].first) {
            j ++; continue;
        }
        ans.push_back(i);
    }
    cout << ans.size() << endl;
    for (int i = 0; i < ans.size(); i ++) cout << ans[i] << " \n"[i == ans.size() - 1];
}

int main() {
    int T = 1;
    // cin >> T;
    while (T --) {
        solve();
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5848kb

input:

3
3 1 8 7
9 1 3 1
5 1 1 6

output:

5
1 3 4 7 8

result:

ok 6 numbers

Test #2:

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

input:

1
1 2
1 2
1 2

output:

2
1 2

result:

ok 3 number(s): "2 1 2"

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 5732kb

input:

252
336470888 634074578 642802746 740396295 773386884 579721198 396628655 503722503 971207868 202647942 2087506 268792718 46761498 443917727 16843338 125908043 691952768 717268783 787375312 150414369 693319712 519096230 45277106 856168102 762263554 674936674 407246545 274667941 279198849 527268921 1...

output:

737
4 5 7 9 10 11 12 14 16 17 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 10...

result:

wrong answer 1st numbers differ - expected: '733', found: '737'