답안 #476178

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
476178 2021-09-25T07:55:14 Z Moeriko_chan Igra (COCI17_igra) C++14
80 / 100
718 ms 65540 KB
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <iomanip>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
//add more if needed-------------------------------------------------//
#define fio ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define rfopen(s) freopen(s, "r", stdin)
#define wfopen(s) freopen(s, "w", stdout)
#define len(a) int(a.size())
#define forw(i, a, b, s) for(int i = a; i < b; i += s)
#define revs(i, a, b, s) for(int i = a; i > b; i -= s)
#define PB push_back
#define EB emplace_back
#define ever ;;
#define FS first
#define SC second
#define PI acos(-1.0)
#define resarr(a) memset(a, 0, sizeof a);
#define allv(v) v.begin(), v.end()
//bit
#define CNTBIT(x) __builtin_popcount(x)
#define ODDBIT(x) __builtin_parity(x)
#define MASK(i) (1<<(i))
#define BIT(x, i) x&MASK(i)
#define SUBSET(big, small) (((big)&(small))==(small))
using namespace std;
namespace io {
    const int SIZE = (1 << 20) + 1;
    char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
    #define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
    inline void flush() { fwrite (obuf, 1, oS - obuf, stdout); oS = obuf; } // print the remaining part
    inline void putc(char x) { *oS++ = x; if (oS == oT) flush (); } // putchar
    template<typename A> inline bool read (A &x) {
        for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1; else if (c == EOF) return 0;
        for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
        return 1;
    }
    inline bool read(char &x) {
        while((x = gc()) == ' ' || x == '\n' || x == '\r'); return x != EOF;
    }
    inline bool read(string& x) {
        while ((c = gc()) == '\n' || c == ' '|| c == '\r'); if (c == EOF) return 0; x.clear();
        while (!(c == '\n' || c == ' ' || c == '\r' || c == EOF)) x.push_back(c), c = gc(); return 1;
    }
    template<typename A,typename ...B>
    inline bool read(A &x, B &...y){ return read(x) + read(y...); }
    template<typename A> inline bool write(A x) {
        if (!x) putc('0'); if (x < 0) putc ('-'), x = -x;
        while (x) qu[++qr] = x % 10 + '0', x /= 10;
        while (qr) putc(qu[qr--]);
        return 0;
    }
    inline bool write(char x) { putc(x); return 0; }
    inline bool write(const char *x){ while (*x){ putc(*x); ++x; } return 0; }
    inline bool write(char *x){ while (*x){ putc(*x); ++x; } return 0; }
    template<typename A,typename ...B>
    inline bool write(A x,B ...y){ return write(x) || write(y...); }
    //no need to call flush at the end manually!
    struct Flusher_ {~Flusher_(){ flush(); }} io_flusher_;
} using io::read; using io::putc; using io::write;
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef pair<ll, ll> pll;
typedef pair<pii, int> pii_i;
typedef pair<int, pii> pi_ii;
typedef pair<int, pll> pi_ll;
typedef pair<float, int> pfi;
typedef pair<ull, pii> pull_ii;
typedef pair<float, pii> pfii;
int divceil(int x, int y){
    return 1 + ((x - 1) / y);
}
//add more if needed-------------------------------------------------//
const int INF = 1e9 + 7;
const ll INF64 = 1e18 + 7;
const float fINF = 340282346638528859811704183484516925439.0000000000000000;
const int N = 5007; ///replace N with the given limit
const int MOD = 1e9 + 7; ///replace this with mod value
int a, b, c, l;
char cr[N];
char ans[N];
set <pii_i> blocked;

bool solvet(int _a, int _b, int _c, int _l){
    //cerr << ans << "\n";
    blocked.insert(pii_i(pii(a, b), c));
    if (_l >= l) return true;
    if (_a > 0 && cr[_l] != 'a' && (blocked.find(pii_i(pii(_a - 1, _b), _c)) == blocked.end() || _l + 1 >= l)){
        ans[_l] = 'a';
        blocked.insert(pii_i(pii(_a - 1, _b), _c));
        if (solvet(_a - 1, _b, _c, _l + 1)) return true;
        ans[_l] = '-';
    }
    if (_b > 0 && cr[_l] != 'b' && (blocked.find(pii_i(pii(_a, _b - 1), _c)) == blocked.end() || _l + 1 >= l)){
        ans[_l] = 'b';
        blocked.insert(pii_i(pii(_a, _b - 1), _c));
        if (solvet(_a, _b - 1, _c, _l + 1)) return true;
        ans[_l] = '-';
    }
    if (_c > 0 && cr[_l] != 'c' && (blocked.find(pii_i(pii(_a, _b), _c - 1)) == blocked.end() || _l + 1 >= l)){
        ans[_l] = 'c';
        blocked.insert(pii_i(pii(_a, _b), _c - 1));
        if (solvet(_a, _b, _c - 1, _l + 1)) return true;
        ans[_l] = '-';
    }
    return false;
}

int main(){
    ///preprocessing
    #ifndef ONLINE_JUDGE
    //rfopen("test.inp");
    //wfopen("test.out");
    #endif // ONLINE_JUDGE
    fio;
    ///codes:
    cin >> l;
    a = b = c = 0;
    for (int i = 0; i < l; i++){
        char r;
        cin >> r;
        switch(r){
        case 'a':
            a++;
            break;
        case 'b':
            b++;
            break;
        case 'c':
            c++;
            break;
        }
    }
    for (int i = 0; i < l; i++){
        cin >> cr[i];
    }
    if (solvet(a, b, c, 0)){
        for (int i = 0; i < l; i++){
            cout << ans[i];
        }
    }
}   

/**
    Must read note before coding ANYTHING!!!:
    - Plan things out before coding (variable names, function names and such) and stay organized
    - Put things that have to be use multiple times into a function
    - Simplify shit as much as possible (still have to be readable)
    - Do something instead of nothing
    - Use note
    - DO NOT STICK TO ONE APPROACH!!!
    Stuff you should look for while debugging:
    - int overflow
    - array bound
    - special cases (n == 1), (n == 0)?
    Read these before doing anything, you"ll thanks me later >^<
    ~(Ruriko, from the Past)~
**/

Compilation message

igra.cpp: In function 'bool io::read(A&)':
igra.cpp:55:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   55 |         for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
      |         ^~~
igra.cpp:55:76: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   55 |         for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
      |                                                                            ^
igra.cpp: In function 'bool io::read(char&)':
igra.cpp:59:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   59 |         while((x = gc()) == ' ' || x == '\n' || x == '\r'); return x != EOF;
      |         ^~~~~
igra.cpp:59:61: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   59 |         while((x = gc()) == ' ' || x == '\n' || x == '\r'); return x != EOF;
      |                                                             ^~~~~~
igra.cpp: In function 'bool io::read(std::string&)':
igra.cpp:62:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   62 |         while ((c = gc()) == '\n' || c == ' '|| c == '\r'); if (c == EOF) return 0; x.clear();
      |         ^~~~~
igra.cpp:62:61: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   62 |         while ((c = gc()) == '\n' || c == ' '|| c == '\r'); if (c == EOF) return 0; x.clear();
      |                                                             ^~
igra.cpp:63:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   63 |         while (!(c == '\n' || c == ' ' || c == '\r' || c == EOF)) x.push_back(c), c = gc(); return 1;
      |         ^~~~~
igra.cpp:63:93: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   63 |         while (!(c == '\n' || c == ' ' || c == '\r' || c == EOF)) x.push_back(c), c = gc(); return 1;
      |                                                                                             ^~~~~~
igra.cpp: In function 'bool io::write(A)':
igra.cpp:68:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   68 |         if (!x) putc('0'); if (x < 0) putc ('-'), x = -x;
      |         ^~
igra.cpp:68:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   68 |         if (!x) putc('0'); if (x < 0) putc ('-'), x = -x;
      |                            ^~
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 9 ms 1784 KB Output is correct
9 Runtime error 718 ms 65540 KB Execution killed with signal 9
10 Runtime error 688 ms 65540 KB Execution killed with signal 9