QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#117914#3221. Clique Coloringi_am_noob#AC ✓2ms3496kbC++141.1kb2023-07-02 14:28:392023-07-02 14:28:42

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-02 14:28:42]
  • Judged
  • Verdict: AC
  • Time: 2ms
  • Memory: 3496kb
  • [2023-07-02 14:28:39]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
#define sz(a) ((int)a.size())
const int mod = 1000'000'007, N = 55, K = 22, C = 28;
int add(int x, int y){x+=y; if(x>=mod) x-=mod; return x;}
int mul(int x, int y){return ((ll)x)*y%mod;}

int n,a[5];
ll res;

vector<int> vec;
void dfs(int cur){
    if(cur==(1<<n)){
        int b[5];
        memcpy(b,a,sizeof a);
        for(auto s: vec) for(int i=0; i<n; ++i) if(s>>i&1) b[i]--;
        bool ok=1;
        for(int i=0; i<n; ++i) if(b[i]<0) ok=0;
        if(ok) res=min(res,sz(vec)+accumulate(b,b+n,0ll));
        return;
    }
    dfs(cur+1);
    if(__builtin_popcount(cur)>1){
        bool ok=1;
        for(auto s: vec) if(__builtin_popcount(cur&s)>1) ok=0;
        if(ok){
            vec.pb(cur);
            dfs(cur+1);
            vec.pop_back();
        }
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    for(int i=0; i<n; ++i) cin >> a[i];
    res=4e18;
    dfs(0);
    cout << res << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1
4

output:

4

result:

ok single line: '4'

Test #2:

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

input:

2
4
1000000000

output:

1000000003

result:

ok single line: '1000000003'

Test #3:

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

input:

3
447893992
4
1000000000

output:

1447893993

result:

ok single line: '1447893993'

Test #4:

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

input:

4
1000000000
1000000000
409299805
305205736

output:

2714505535

result:

ok single line: '2714505535'

Test #5:

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

input:

5
701636407
83399801
260677870
1000000000
4

output:

2045714072

result:

ok single line: '2045714072'

Test #6:

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

input:

1
3

output:

3

result:

ok single line: '3'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3388kb

input:

2
497280904
3

output:

497280906

result:

ok single line: '497280906'

Test #8:

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

input:

3
3
4
495505982

output:

495505986

result:

ok single line: '495505986'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3408kb

input:

4
4
3
4
4

output:

9

result:

ok single line: '9'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3484kb

input:

5
4
4
3
4
1000000000

output:

1000000006

result:

ok single line: '1000000006'

Test #11:

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

input:

2
3
3

output:

5

result:

ok single line: '5'

Test #12:

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

input:

3
1000000000
3
3

output:

1000000003

result:

ok single line: '1000000003'

Test #13:

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

input:

4
378634918
3
3
4

output:

378634922

result:

ok single line: '378634922'

Test #14:

score: 0
Accepted
time: 2ms
memory: 3408kb

input:

5
693604254
3
3
1000000000
4

output:

1693604255

result:

ok single line: '1693604255'

Test #15:

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

input:

3
3
3
3

output:

6

result:

ok single line: '6'

Test #16:

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

input:

4
3
3
741443949
3

output:

741443952

result:

ok single line: '741443952'

Test #17:

score: 0
Accepted
time: 2ms
memory: 3456kb

input:

5
798458902
3
3
85709420
3

output:

884168322

result:

ok single line: '884168322'

Test #18:

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

input:

4
3
3
3
3

output:

6

result:

ok single line: '6'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3384kb

input:

5
3
3
4
3
3

output:

8

result:

ok single line: '8'

Test #20:

score: 0
Accepted
time: 0ms
memory: 3392kb

input:

5
3
3
3
3
3

output:

7

result:

ok single line: '7'

Test #21:

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

input:

1
2

output:

2

result:

ok single line: '2'

Test #22:

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

input:

2
1000000000
2

output:

1000000001

result:

ok single line: '1000000001'

Test #23:

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

input:

3
275630553
2
1000000000

output:

1275630552

result:

ok single line: '1275630552'

Test #24:

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

input:

4
4
85561698
2
4

output:

85561703

result:

ok single line: '85561703'

Test #25:

score: 0
Accepted
time: 2ms
memory: 3460kb

input:

5
343830664
2
266706206
477214206
4

output:

1087751074

result:

ok single line: '1087751074'

Test #26:

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

input:

2
2
3

output:

4

result:

ok single line: '4'

Test #27:

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

input:

3
2
3
1000000000

output:

1000000002

result:

ok single line: '1000000002'

Test #28:

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

input:

4
3
2
277873868
1000000000

output:

1277873868

result:

ok single line: '1277873868'

Test #29:

score: 0
Accepted
time: 2ms
memory: 3384kb

input:

5
2
136812254
473248215
3
4

output:

610060470

result:

ok single line: '610060470'

Test #30:

score: 0
Accepted
time: 0ms
memory: 3404kb

input:

3
3
2
3

output:

5

result:

ok single line: '5'

Test #31:

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

input:

4
3
2
1000000000
3

output:

1000000003

result:

ok single line: '1000000003'

Test #32:

score: 0
Accepted
time: 2ms
memory: 3392kb

input:

5
2
3
261722051
3
1000000000

output:

1261722051

result:

ok single line: '1261722051'

Test #33:

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

input:

4
3
3
3
2

output:

6

result:

ok single line: '6'

Test #34:

score: 0
Accepted
time: 2ms
memory: 3456kb

input:

5
3
3
857509551
3
2

output:

857509554

result:

ok single line: '857509554'

Test #35:

score: 0
Accepted
time: 2ms
memory: 3388kb

input:

5
3
3
3
2
3

output:

6

result:

ok single line: '6'

Test #36:

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

input:

2
2
2

output:

3

result:

ok single line: '3'

Test #37:

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

input:

3
2
1000000000
2

output:

1000000001

result:

ok single line: '1000000001'

Test #38:

score: 0
Accepted
time: 0ms
memory: 3404kb

input:

4
615064899
2
2
4

output:

615064902

result:

ok single line: '615064902'

Test #39:

score: 0
Accepted
time: 2ms
memory: 3388kb

input:

5
4
1000000000
1000000000
2
2

output:

2000000001

result:

ok single line: '2000000001'

Test #40:

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

input:

3
2
3
2

output:

4

result:

ok single line: '4'

Test #41:

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

input:

4
4
2
3
2

output:

6

result:

ok single line: '6'

Test #42:

score: 0
Accepted
time: 0ms
memory: 3448kb

input:

5
2
3
1000000000
4
2

output:

1000000004

result:

ok single line: '1000000004'

Test #43:

score: 0
Accepted
time: 0ms
memory: 3456kb

input:

4
2
3
2
3

output:

5

result:

ok single line: '5'

Test #44:

score: 0
Accepted
time: 2ms
memory: 3444kb

input:

5
2
3
54069329
2
3

output:

54069332

result:

ok single line: '54069332'

Test #45:

score: 0
Accepted
time: 2ms
memory: 3460kb

input:

5
3
3
3
2
2

output:

6

result:

ok single line: '6'

Test #46:

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

input:

3
2
2
2

output:

3

result:

ok single line: '3'

Test #47:

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

input:

4
2
4
2
2

output:

5

result:

ok single line: '5'

Test #48:

score: 0
Accepted
time: 0ms
memory: 3380kb

input:

5
2
2
395669578
2
906198920

output:

1301868497

result:

ok single line: '1301868497'

Test #49:

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

input:

4
3
2
2
2

output:

4

result:

ok single line: '4'

Test #50:

score: 0
Accepted
time: 0ms
memory: 3396kb

input:

5
3
2
1000000000
2
2

output:

1000000002

result:

ok single line: '1000000002'

Test #51:

score: 0
Accepted
time: 2ms
memory: 3388kb

input:

5
2
3
2
3
2

output:

5

result:

ok single line: '5'

Test #52:

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

input:

4
2
2
2
2

output:

4

result:

ok single line: '4'

Test #53:

score: 0
Accepted
time: 2ms
memory: 3384kb

input:

5
2
2
2
1000000000
2

output:

1000000001

result:

ok single line: '1000000001'

Test #54:

score: 0
Accepted
time: 2ms
memory: 3388kb

input:

5
2
2
2
3
2

output:

5

result:

ok single line: '5'

Test #55:

score: 0
Accepted
time: 0ms
memory: 3384kb

input:

5
2
2
2
2
2

output:

4

result:

ok single line: '4'

Test #56:

score: 0
Accepted
time: 2ms
memory: 3388kb

input:

5
1000000000
1000000000
1000000000
1000000000
1000000000

output:

4999999990

result:

ok single line: '4999999990'

Test #57:

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

input:

2
3
3

output:

5

result:

ok single line: '5'

Test #58:

score: 0
Accepted
time: 2ms
memory: 3392kb

input:

5
2
3
4
5
6

output:

12

result:

ok single line: '12'